LeetCode 88. Merge Sorted Array [Easy] [C++] 解題筆記

這題給定兩個在第 m 與第 n 個元素前已經排序好的陣列 nums1, nums2，要我們將兩個陣列合併到 nums1 中並排序好。(nums1 保證有足夠的空間存放 m + n)。

EX:

        nums1 = [4, 5, 6, 0, 0, 0]

        

        nums2 = [1, 2, 3]

Ans: nums1 = [1, 2, 3, 4, 5, 6]

想法:

        合併兩個排序好的 array 其實就是 merge sort 在 merge 的時候用到的技巧，我們只需要用兩個 index 逐個比較兩個 array 的元素，每次將較小的放入新的 array 就好，這題比較不一樣的是題目已經保證 nums1 有足夠空間並要求更新在 nums1，因此我們要反過來比較，從尾端到前端逐個比較 nums1 與 nums2 的元素然後將較大的放到 nums1 尾端。

Complexity: O(n) time, O(1) space

完整程式碼:

class Solution {

public:

    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

        int p1 = m - 1;

        int p2 = n - 1;

        int cur = m + n - 1;

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

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

                nums1[cur--] = nums1[p1--];

            }

            else {

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

            }

        }

        while (p2 >= 0) {

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

        }

        return;

    }

};