88. Merge Sorted Array

二刷 06/2022

Version #2 Merge from the largest numbers

Time O(M + N)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Sorted Array.

Memory Usage: 41.9 MB, less than 96.28% of Java online submissions for Merge Sorted Array.

class Solution {

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

        int p = m + n - 1;

        int p1 = m - 1;

        int p2 = n - 1;

        while (p1 >= 0 && p2 >= 0) {

            if (nums1[p1] > nums2[p2]) {

                nums1[p--] = nums1[p1--];

            } else {

                nums1[p--] = nums2[p2--];

            }

        }

        // Already in place, can be skipped

        // while (p1 >= 0) {

        //     nums1[p--] = nums1[p1--];

        // }

        while (p2 >= 0) {

            nums1[p--] = nums2[p2--];

        }

    }

}

Version #1 Move nums1 elements to the end of the array and merge from small elements - not optimal

此处写了一个bug，就是如果nums1是从小到大move，那么当nums2比nums1短的时候，就是发生nums1自己overwrite自己的情况

e.g.

[1,2,4,5,6,0]

5
[3]
1

所以此处nums1要从end开始move

当然看了答案发现可以从end开始merge，是更优的解法

Time O(M + N)

Space O(1)

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Sorted Array.

Memory Usage: 43 MB, less than 36.08% of Java online submissions for Merge Sorted Array.

class Solution {

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

        if (n == 0) {

            return;

        }

        int p1 = n;

        for (int i = m - 1; i >= 0; i--) {

            nums1[i + n] = nums1[i];

        }

        int p = 0;

        p1 = n;

        int p2 = 0;

      

        while (p1 < m + n && p2 < n) {

            if (nums1[p1] < nums2[p2]) {

                nums1[p++] = nums1[p1++];

            } else {

                nums1[p++] = nums2[p2++];

            }

        }

        while (p1 < m + n) {

            nums1[p++] = nums1[p1++];

        }

        while (p2 < n) {

            // System.out.printf("p=%d, p2=%d, n=%d", p, p2, n);

            nums1[p++] = nums2[p2++];

        }

        

    }

}

一刷

为了不污染nums1的数据 -> 从大到小merge
一个 bug
如果nums1里面的数都merge完毕了-> p1 = -1 -> nums2还没有merge完
则需要继续向里面merge
此时就一个一个的把nums2里面的数放到nums1里面
所以判断是 p1 >= 0 或 nums1[p1] > nums2[p2]
99.99 %
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p = m + n - 1;
        int p1 = m - 1;
        int p2 = n - 1;
        while (p2 >= 0) {
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }
    }
}