合并两个有序数组（Merge-Sorted-Array）

题干：

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
来源：力扣（LeetCode）

这是一题关于数组的题目。目前为止讲解数组、字符串相关的题目都会引入一个解题思路： 双指针思路。其实就是想让小伙伴们培养一个习惯：面对数组、字符串类型的题目先用 双指针思路 来捣腾捣腾。

当然这题也是引用这个思路来解题，只不过这时候的 双指针 不在指向一个数组，而是分别指向数组 num1 和 num2。

解题思路

简单粗暴的方式就是将 num1 和 num2 直接合并，再重新排序，当然不建议这么做啦。

我们仔细审一下题：题目告诉我们 num1 和 num2 是有序的，并且是从小到大排序的。那我们是不是可以从左到右依次比较 num1 和 num2 中的元素值，并将 较小的值minV 逐一存储到一个新的数组 num3 中。

但是题目有一个限制：需要将 num2 直接合并到 num1 中。这时候我们发现用从左到右的方式遍历，并将 minV 插入到 num1 中势必会产生挪动 num1 元素的操作，例如：需要在 num1 索引为 2 的位置插入 minV，那么需要将原本 索引为 2 的元素以及之后的元素都向后挪一位，空出索引为 2 的位置。成本有点大，并且也不好实现。

那么如何解决上面的问题呢？其实换成从右向左遍历就行啦。我们知道 num1 现在的长度为 m，当前最大索引记为 i ， num2 的长度为 n，当前最大索引记为 j，合并之后 num1 的长度应该是 m + n，最大索引记为 max。我们比较 num1[i] 与 num2[j] 的大小，如果 num1[i] 大于 num2[j] ，那么 num1[max] = num1[i]，max 向左移动一位，i 向左移动一位，反之 num1[max] = num2[j]，max 向左移动一位，j 向左移动一位。重复上面的操作，具体流程以及一些边界问题，查看下面的流程图：

代码实现

func merge(nums1 []int, m int, nums2 []int, n int) {

    // max 指向 nums1 与 nums2 合并之后的最后一个元素
    max := m + n - 1

    // 指向 num1 最后一个元素
    i := m - 1

    // 指向 num2 最后一个元素
    j := n -1


    for i >= 0 && j >= 0 {

        // 从右向左比较值的大小
        if nums1[i] > nums2[j] {
            nums1[max] = nums1[i]

            // i 向左移动
            i--
        } else {
            nums1[max] = nums2[j]

            // j 向左移动
            j--
        }

        // max 向左移动
        max --




    }

    // 如果 i 越界了，将 nums2 剩余的元素赋值到 num1 的 [0,m] 之间
    for j >= 0 {
        nums1[max] = nums2[j]
        max--
        j--
    }

    // 如果 j 越界了，其实下面这个循环可以省略。
    for i >= 0 {
        nums1[max] = nums1[i]
        max--
        i--
    }
}

总结

每天进步一点点，加油！

下面是编程之家 jb51.cc 通过网络收集整理的代码片段。

编程之家小编现在分享给大家，也给大家做个参考。

给定含有m、n个元素的两个有序(非降序)整型数组a和b。

合并两个数组中的元素到整型数组c，要求去除重复元素并保持c有序(非降序)。

例子如下：

a = 2,3,4,6,8,9

b = 7,9,10

c = 2,7,10

// 合并两个含有nA、nB个元素的有序数组

void Merge(int *a,int *b,int *c,int nA,int nB,int& nCout)

{

int i = 0 ;

int j = 0 ;

int k = 0 ;

while (i < nA && j < nB)

{

if (a[i] < b[j])// 如果a的元素小，则插入a中元素到c

{

c[k++] = a[i] ;

++i ;

nCout++;

}

else if (a[i] == b[j])// 如果a和b元素相等，则插入二者皆可，这里插入a

{

c[k++] = a[i] ;

++i ;

++j ;

nCout++;

}

else // a[i] > b[j] // 如果b中元素小，则插入b中元素到c

{

c[k++] = b[j] ;

++j ;

nCout++;

}

}

if (i == nA) // 若a遍历完毕，处理b中剩下的元素

{

for (int m = j; m < nB; ++m)

{

c[k++] = b[m] ;

nCout++;

}

}

else//j == n,若b遍历完毕，处理a中剩下的元素

{

for (int m = i; m < nA; ++m)

{

c[k++] = a[m] ;

nCout++;

}

}

}

测试代码

int main()

{

int* a= new int[6];

int* b= new int[3];

a[0]=2;

a[1]=3;

a[2]=4;

a[3]=6;

a[4]=8;

a[5]=9;

b[0]=7;

b[1]=9;

b[2]=10;

int nOut = 0;

int* output = new int[12];

Merge(a,b,output,nOut);

for (int i=0; i

{

cout << output[i] << "," ;

}

cout << endl;

delete[] a;

a=NULL;

delete[] b;

b=NULL;

delete[] output;

output=NULL;

cout << endl;

return 0;

}

以上是编程之家(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得编程之家网站内容还不错，欢迎将编程之家网站推荐给程序员好友。

总结

以上是编程之家为你收集整理的C语言合并两个数组并去重全部内容，希望文章能够帮你解决C语言合并两个数组并去重所遇到的程序开发问题。

如果觉得编程之家网站内容还不错，欢迎将编程之家网站推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

小编个人微信号 jb51ccc

喜欢与人分享编程技术与工作经验，欢迎加入编程之家官方交流群！

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例：

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

题解分析

方法一：直接合并

将 num2的元素直接添加到 nums1中后，再进行排序，此方法简单，但是时间复杂度比较差

class 

执行结果

方法二：双指针法

此题目其实是可以使用双指针的方式

指定两个指针p1, p2分别代表 m-1及n-1即数组 nums1及 nums2的最后下标，p 则是 m+n-1。

当 nums1[p1] < nums2[p2]时，将 nums2[p2]的值放入nums[p]中， 同时 p、p2向左移，即 p--、p2--;

当 nums1[p1] > nums2[p2]时，则将 num1[p1]的值放入 nums[p]中，同时p、p1向左移，即 p--、p1--;

最后再将nums2多余的数据复制至 num1的开头即可（因为是有序的且都比nums1的值小，直接复制过来就可以）

第一步：

第二步：

第三步：

后面依此类推，即可

class 

执行结果