88. 合并两个有序数组

给你两个有序整数数组 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） 链接：https://leetcode-cn.com/problems/merge-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

nums1 为结果数组且有足够的空间，把nums2的结果逐步插入nums1合适的位置即可，从后往前（从大到小）依次把nums2的元素合并到nums1中即可。

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m + n - 1;
        int idx1 = m - 1;
        int idx2 = n - 1;

        while (idx1 >=0 || idx2 >= 0){

            if (idx2 < 0){
                break;
            }

            if (idx1 < 0){
                while (idx2 >= 0){
                    nums1[index --] = nums2[idx2 --];
                }
                continue;
            }

            if (nums1[idx1] > nums2[idx2]){
                nums1[index --] = nums1[idx1 --];
            }else {
                nums1[index--] = nums2[idx2--];
            }
        }
    }

时间复杂度： O(N ^ 2)

空间复杂度： O(1)