LeetCode-88题合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

题解1

直接将两个数组相加，采用java.util下的 Arrays.sort() 方法重新排序，简单有效。

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }
        Arrays.sort(nums1);
    }

Arrays.sort小数组底层-插入排序

采用数组nums={1，4，7，2，5，6}作为例子

1.将数组传入快速排序中排序；

2.数组长度减1小于286的进入这个排序方法；

3.很明显数组长度小于47的时候则优先使用插入排序

4.按左边进行插入排序：

① 当数组中的两个元素进行比较大小时，先取出右边的元素存入ai中，

② 将右边的元素与左边的元素进行比较；

Ⅰ、如果右边的元素大于等于左边的元素，则插入原位置；

Ⅱ、若果右边的元素小于左边的元素，会将左边所有大于右边的元素后移一位，循环一次则指针索引 j--，代表右边的元素前移一位，最终覆盖原有元素。

时间复杂度为O( (m+n)log(m+n) )。

题解2

采用双指针和临时数组的方法对两数组排序；

1. 同时遍历两个数组，如果nums1中取出的元素小于nums2中取出的元素，则将nums1中的元素放入临时数组；
2. 如果nums1中取出的元素大于等于nums2中取出的元素，则将nums2中的元素放入临时数组；
3. 将临时数组中的元素放入nums1中；

时间复杂度O（m+n），空间复杂度O(m+n);

public void merge(int[] nums1, int m, int[] nums2, int n) {
        //建立临时数组
        int k = m + n;
        int[] temp = new int[k];

        //循环数组，建立双指针比较
        for (int i = 0, nums1Index = 0, nums2Index = 0; i < k; i++) {
            //数组1中指针超过索引长度，代表数组1的元素已取完则将数组2中元素放入临时数组
            if (nums1Index >= m) {
                temp[i] = nums2[nums2Index++];
            } else if (nums2Index >= n) {
                //数组2中指针超过索引长度，则将数组1中的元素放入临时数组
                temp[i] = nums1[nums1Index++];
            } else if (nums1[nums1Index] < nums2[nums2Index]) {
                //如果数组1中指针指的元素小于数组2中指针指的元素，将数组1中的元素放入临时数组
                temp[i] = nums1[nums1Index++];
            } else {
                //数组1中指针指的元素大于等于数组2中指针指的元素，将数组2的元素放入临时数组
                temp[i] = nums2[nums2Index++];
            }
        }
        //将临时数组放入数组1中
        for (int i = 0; i < temp.length; i++) {
            nums1[i] = temp[i];
        }

题解2优化

1. 题解2中是创造了一个临时数组，其实数组nums1中的长度为m+n可以将两个数组同时放入的；
2. 采用双指针和一个数组的方法；
3. 取出两个数组指向的元素，元素大的倒序放入nums1数组中。

时间复杂度O（m+n），空间复杂度O(1);

 public void merge3(int[] nums1, int m, int[] nums2, int n) {
        //nums1有效元素为m个，但nums1的初始长度为m+n，我们可以将两个数组比较大的元素放入数组1中后面的位置
        for (int i = m + n - 1, nums1Index = m - 1, nums2Index = n - 1; i >= 0; i--) {
            if (nums1Index < 0) {
                //如果nums1中的指针小于0，则代表nums1中元素已经没有了，将nums2中的元素放入nums1中的指定位置
                nums1[i] = nums2[nums2Index--];
            } else if (nums2Index < 0) {
                //如果nums2中的指针小于0，直接退出即可，
                break;
            } else if (nums1[nums1Index] <= nums2[nums2Index]) {
                //如果nums2中的元素大于等于nums1中的元素，将nums2中的元素放入数组对应位置
                nums1[i] = nums2[nums2Index--];
            } else {
                //如果nums2中的元素小于nums1中元素，将nums1中的元素取出放入对应位置
                nums1[i] = nums1[nums1Index--];
            }
        }
    }