![【每日算法 && 数据结构(C++)】—— 03 | 合并两个有序数组(解题思路、流程图、代码片段)](https://imgs.yssmx.com/Uploads/2023/06/507991-1.gif)
An inch of time is an inch of gold, but you can’t buy that inch of time with an inch of gold.
01 | 👑 题目描述
给你两个有序数组,请将两个数组进行合并,并且合并后的数组也必须有序
这个题目要求将两个有序数组合并成一个有序数组。在数学上,我们可以使用归并排序的思想来解决这个问题。
02 | 🔋 解题思路
假设给定的两个有序数组分别为 arr1
和 arr2
,长度分别为 n1
和 n2
。我们可以创建一个新的数组 result
,长度为 n1 + n2
,用于存储合并后的有序数组。
我们可以使用两个指针 i
和 j
分别指向 arr1
和 arr2
的起始位置。然后,我们比较这两个指针所指向的元素,并将较小的元素加入到 result
数组中。然后根据比较结果,移动相应的指针。
具体的步骤如下:
- 创建一个新的数组
result
,长度为n1 + n2
。 - 初始化指针
i
和j
分别为 0,指向arr1
和arr2
的起始位置。 - 使用循环,比较
arr1[i]
和arr2[j]
的大小:- 如果
arr1[i] < arr2[j]
,将arr1[i]
加入到result
数组中,然后将指针i
向后移动一位。 - 如果
arr1[i] > arr2[j]
,将arr2[j]
加入到result
数组中,然后将指针j
向后移动一位。 - 如果
arr1[i] = arr2[j]
,将arr1[i]
和arr2[j]
分别加入到result
数组中,然后将指针i
和j
都向后移动一位。 - 重复上述步骤,直到其中一个数组的元素全部加入到
result
数组中。
- 如果
- 将剩余未加入
result
数组的元素依次加入。 - 返回合并后的有序数组
result
。
-
时间 && 空间复杂度
-
时间复杂度:O(n1 + n2)
其中 n1 和 n2 分别是两个有序数组的长度。这是因为我们需要将两个数组中的所有元素逐个比较和复制到新的数组中 -
空间复杂度:O(n1 + n2)
因为我们需要创建一个大小为 n1 + n2 的新数组来存储合并后的有序数组
-
03 | 🧢 代码片段
#include <iostream>
#include <vector>
std::vector<int> mergeSortedArrays(const std::vector<int>& arr1, const std::vector<int>& arr2) {
std::vector<int> mergedArray;
int i = 0; // 指向arr1的指针
int j = 0; // 指向arr2的指针
// 比较arr1和arr2中的元素,将较小的元素加入到mergedArray中
while (i < arr1.size() && j < arr2.size()) {
if (arr1[i] < arr2[j]) {
mergedArray.push_back(arr1[i]);
i++;
} else {
mergedArray.push_back(arr2[j]);
j++;
}
}
// 将剩余未加入mergedArray的元素依次加入
while (i < arr1.size()) {
mergedArray.push_back(arr1[i]);
i++;
}
while (j < arr2.size()) {
mergedArray.push_back(arr2[j]);
j++;
}
return mergedArray;
}
int main() {
std::vector<int> arr1 = {1, 3, 5, 7, 9};
std::vector<int> arr2 = {2, 4, 6, 8, 10};
std::vector<int> mergedArray = mergeSortedArrays(arr1, arr2);
std::cout << "Merged Array: ";
for (int num : mergedArray) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
文章来源:https://www.toymoban.com/news/detail-507991.html
文章来源地址https://www.toymoban.com/news/detail-507991.html
到了这里,关于【每日算法 && 数据结构(C++)】—— 03 | 合并两个有序数组(解题思路、流程图、代码片段)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!