leetcode 88 Merge Sorted Array
z
 2017-12-24 19:51:16  

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

最初始的想法是从前往后遍历，找到一个nums1[i] > nums2[j]，把nums1从i开始后移一位。但是这样的时间复杂度较高

再然后适用一个新的数组result[m+n]，时间复杂度为O(m+n)，但是空间复杂度也有O(m+n)

再考虑从后往前遍历两个数组，时间复杂度为O(m+n), 空间复杂度为O(1).

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
26
27
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m-1;
        int j = n-1;
        int k = m+n-1;
        while(k > i && k > j){
            if(nums1[i] <= nums2[j]){
                nums1[k] = nums2[j];
                k--;
                j--;
            }
            else{
                nums1[k] = nums1[i];
                i--;
                k--;
            }
        }
      // 上面循环结束的条件是k=i或者k=j;
      // 如果k=i，说明num1从第k位开始，前面的数都应该从nums1中获取，因此不需要再操作
      // 如果k=j，说明num1从第k为开始，前面的数都应该从nums2中获取，因此循环将nums2中的数赋值给nums1
        while(j>=0){
            nums1[k] = nums2[j];
            k--;
            j--;
        }
    }
}