Leetcode 88. Merge Sorted Array

給定兩個排序好的整數列表 nums1 和 nums2 ，並且給定兩個整數 m 和 n ，分別代表了 nums1 和 nums2 的長度，題目要求我們將這兩個已經排序好的整數列表進行合併，返回一個升序的整數列表

Python

方法一 : 雙指針

當 n 為 0 的時候，表示 nums1 不需要和 nums2 進行合併，不管 nums1 是什麼，直接返回 nums1
當 m 為 0 的時候，表示 nums1 為空，沒有需要合併的元素，但是此時不能直接返回 nums2 ，因為題目要求最後返回的是 nums1 ，所以不管 nums2 有多少元素，直接賦值給 nums1 ，然後再返回 nums1
從 nums1 的最後一個元素和 nums2 的最後一個元素開始逆向比較大小：
- 如果 nums1[m-1] 大於等於 nums2[n-1] ，則將 nums1[m-1] 賦值給 nums1[m+n-1] ，同時 m 減一
- 否則將 nums2[n-1] 賦值給 nums1[m+n-1] ，同時 n 減一
如果 nums2 先遍歷結束，因為 nums1 剩下的元素一開始就是有序的，所以不用管他，但如果 nums 1 先遍歷結束，可能 nums2 還有剩下的元素沒有遍歷，因為 nums2 剩下的元素一開始就是有序的，直接將 nums2[:n] 賦值給 nums1[:n] 即可

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        if n == 0: 
            return nums1
        if m == 0: 
            nums1[:n] = nums2[:n]
            return nums1
        while m>0 and n>0:
            if nums1[m-1]>=nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        nums1[:n] = nums2[:n]
        return nums1

方法一 : 三指針

從 nums1 的最後一個元素和 nums2 的最後一個元素開始逆向比較大小，如果 nums1[i] 大於 nums2[j] ，則將 nums1[i] 賦值給 nums1[k](尾端)，同時 i 減一，否則將 nums2[j] 賦值給 nums1[k] ，同時 j 減一，之後k減1，往前繼續比較。如果 nums 1 先遍歷結束， nums2 還有剩下的元素沒有遍歷，把nums2剩下的元素加入nums1，之後k減1，j減1。

class Solution(object): 
    def merge(self, nums1, m, nums2, n): 
        i, j = m - 1, n - 1 
        k = m + n - 1 
        while i >= 0 and j >= 0: 
            if nums1[i] > nums2[j]: 
                nums1[k] = nums1[i] 
                i -= 1 
            else: 
                nums1[k] = nums2[j] 
                j -= 1 
            k -= 1 
        while j >= 0: 
            nums1[k] = nums2[j]
            j -= 1 
            k -= 1

C++

從後向前遍歷。指針 i 和 j 分別指向 nums1 和 nums2 的最後一個元素，指針 k 指向 nums1 的最後一個位置。比較 nums1[i] 和 nums2[j] 的大小，將較大的元素存入 nums1[k] 中，指針 k 和較大元素的指針向前移動一位，直到 nums2 中所有的元素都被合併到 nums1 中為止。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int p = m + n - 1;
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] >= nums2[p2]) {
                nums1[p--] = nums1[p1--];
            } else {
                nums1[p--] = nums2[p2--];
            }
        }
        while (p2 >= 0) {
            nums1[p--] = nums2[p2--];
        }
    }
};

Python

C++

相關