By

前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、两个有序数组合并成一个数组

1.1、题目1

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

说明: 初始化 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]

1.1.1、解题思路

从后往前双指针

1.1.2、算法

1.1.2、算法

@Test
public void test() {
    int nums1[] = {2, 3, 4, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int nums2[] = {1, 2, 3};
    merge(nums1, 4, nums2, 3);
    System.out.println(Arrays.toString(nums1));
}

public void merge(int[] nums1, int m, int[] nums2, int n) {
    //新数组最大的索引位
    int x = (m--) + (n--) - 1 ;
    while(m >= 0 && n >= 0){
        nums1[x--] = nums1[m] > nums2[n] ? nums1[m--]  : nums2[n--];
    }
    
    //m是不会有剩余的，m可以直接在上面搞完
    while (n >= 0) {
        nums1[x--] = nums2[n--];
    }
}

1.2、题目2

数组A (9,8,7,6,5,4,2,1)

数组B (8,5,4,3,4,6)

将上面的两个数组合并成一个数组，最快的方法

1.2.1、解题思路

将上面的两个数组合并成一个数组，最快的方法

新建一个数组C ，上面开头的两个数组，依次比较大小，大的放进来，9先进入，指针移动到8，然后8再和下面的进行比较，相同，分别移动进来，然后A数组指针移动饿到7，数组B指针移动到5，依次执行

1.3.2、算法-


/**
题目：两个有序数组合并成一个数组
    数组A (9,8,7,6,5,4,2,1)
    数组B (8,5,4,3,4,6)
解题思路：
    新建一个数组C ，上面开头的两个数组，依次比较大小，大的放进来，9先进入，指针移动到8，然后8再和下面的进行比较，相同，分别移动进来，然后A数组指针移动饿到7，数组B指针移动到5，依次执行
 */
public class D01两个有序数组合并成同一个 {

    @Test
    public void test() {
        int a[] = {7, 6, 5, 4, 3, 2, 1, 0};
        int b[] = {9, 9, 9, 9, 8, 5, 3, 2};
        int c[] = new int[a.length + b.length], i = 0, j = 0, n = 0;
        //保证两个数组同时遍历
        while (i < a.length && j < b.length) {
            if (a[i] > b[j]) {
                c[n] = a[i];
                i++;
            } else {
                c[n] = b[j];
                j++;
            }
            n++;
        }

        //上面有一方会提前结束
        while (i < a.length) {
            c[n] = a[i];
            i++;
            n++;
        }

        while (j < b.length) {
            c[n] = b[j];
            j++;
            n++;
        }

        System.out.println(Arrays.toString(c));
    }


}

ContactAuthor