[LeetCode] 88. Merge Sorted Array

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

解题想法

题目要求要 in-place 完成此题，最后结果储存至 nums1 里头。
方法是透过三个 pointer 合作

由后往前看，判断较大的直线放在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