C++ 非递减序列 二路归并

本文主要是介绍C++ 非递减序列 二路归并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

一、二路归并 源码

void merge(vector<int>& num1, int m, vector<int>& num2, int n)
{vector<int> merged(m + n, 0);int i = 0, j = 0, k = 0;while (i < m && j < n){if (num1[i] < num2[j]){merged[k++] = num1[i++];}else{merged[k++] = num2[j++];}}while (i < m){merged[k++] = num1[i++];}while (j < n){merged[k++] = num2[j++];}num1 = merged;
}

二、算法思路：

首先创建一个新的数组 merged 来存储合并后的结果。
然后使用三个指针 i、j、k 分别指向 nums1、nums2 和 merged 的当前位置。
通过比较 nums1[i] 和 nums2[j] 的大小来选择较小的元素放入 merged 中，并逐步移动指针 i、j 和 k。
而后将剩余未处理的元素依次加入到 merged 中。
最后将 nums1 赋值为合并后的结果 merged，即完成了两个非递减序列的合并。

三、完整源码：

#include <iostream>
#include <vector>using namespace std;void merge(vector<int>& num1, int m, vector<int>& num2, int n)
{vector<int> merged(m + n, 0);int i = 0, j = 0, k = 0;while (i < m && j < n){if (num1[i] < num2[j]){merged[k++] = num1[i++];}else{merged[k++] = num2[j++];}}while (i < m){merged[k++] = num1[i++];}while (j < n){merged[k++] = num2[j++];}num1 = merged;
}int main()
{vector<int> num1 = { 1,3,5,0,0,0 };int m = 3;vector<int> num2 = { 2,4,6 };int n = 3;merge(num1, m, num2, n);for (int num : num1){cout << num << " ";}return 0;
}

四、知识点小笔记：

1.vector merged(m + n, 0);

在代码中，vector<int> merged(m + n, 0); 其作用是创建一个名为 merged 的 std::vector 对象，其中包含 m + n 个元素，每个元素的初始值都是 0。

vector<int>：表示要创建一个存储整数类型的向量（即数组）。
merged：新向量选择的名称。
(m + n, 0)：向量构造函数的参数。(m + n, 0) 表示创建一个包含 m + n 个元素的向量，并且所有元素的初始值都是 0。

因此，vector<int> merged(m + n, 0);是创建了一个包含 m + n 个元素的整数向量 merged，并且所有元素的初始值都是 0。该向量将用于存储合并后的结果。

2.for (int num : nums1)

for (int num : nums1) 是 C++11 中引入的一种新的循环语法，称为range-based for loop。该循环语法使得遍历容器（如向量、数组等）中的元素变得更加简洁和直观。

在这个循环中，int num 是循环变量的声明，它会在每次迭代中依次取 nums1 中的元素值。而 nums1 则是我们要遍历的容器，这里是一个 std::vector<int> 类型的向量。

因此，for (int num : nums1) 是遍历 nums1 中的每个元素，并将当前元素赋值给 num，然后执行循环体内的操作。这种循环语法在遍历容器时非常方便，可以让代码更加简洁易读。

3.vector nums1 = {1, 3, 5, 0, 0, 0}; int m = 3;

在很多情况下，处理数组或向量时，正常会使用一个额外的变量（如 m）来标记有效元素的数量，而后面的元素被视为无效或者是用来填充的。该方式在实际编程中非常常见，特别是在处理固定大小的数组或向量时。
因此，当你int m = 3; 时，程序中处理 nums1 的部分会自动忽略后面的 0 元素，在这种情况下，只有前 m 个元素会被看作有效元素。

这篇关于C++ 非递减序列 二路归并的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---