Easy
Related Topics: Array / Two Pointers / Sorting
LeetCode Source

解題想法

題目要求要 in-place 完成此題，最後結果儲存至 nums1 裡頭。
方法是透過三個 pointer 合作

• 一個代表nums1: index1 = m - 1
• 一個代表nums2: index2 = n - 1
• 還有一個total: total = m - n + 1，代表nums1要被存入的 index

由後往前看，判斷較大的直線放在nums1最後面含零的位置，巧妙解決會發生儲存值會衝突的情形
最後面判斷如果index2還大於等於零，即nums2還有值時的情形，將剩餘的值存入nums1

Python

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        index1 = m - 1
        index2 = n - 1
        total = m + n - 1

        while index1 >= 0 and index2 >= 0:
            if nums1[index1] >= nums2[index2]:
                nums1[total] = nums1[index1]
                index1 -= 1
            else:
                nums1[total] = nums2[index2]
                index2 -= 1
            total -= 1

        while index2 >= 0:
            nums1[total] = nums2[index2]
            index2 -= 1
            total -= 1

C++

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int index1 = m - 1, index2 = n - 1, total = m + n - 1;

        while (index1 >= 0 && index2 >= 0) {
            if (nums1[index1] >= nums2[index2]) {
                nums1[total] = nums1[index1];
                index1 -= 1;
            } else {
                nums1[total] = nums2[index2];
                index2 -= 1;
            }
            total -= 1;
        } 

        while (index2 >= 0) {
            nums1[total] = nums2[index2];
            index2 -= 1;
            total -= 1;
        }
    }
};

這系列文被記錄在 Top Interview 150 Series