LeetCode #88 2018-07-28

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:

• The number of elements initialized in nums1 and nums2 are m and n respectively.
• You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

https://leetcode.com/problems/merge-sorted-array/description/

这道题思路比较明确，就是维护三个index，分别对应数组A，数组B，和结果数组。然后A和B同时从后往前扫，每次迭代中A和B指向的元素大的便加入结果数组中，然后index-1，另一个不动。这里从后往前扫是因为这个题目中结果仍然放在A中，如果从前扫会有覆盖掉未检查的元素的可能性。算法的时间复杂度是O(m+n),m和n分别是两个数组的长度，空间复杂度是O(1)。
代码如下：

class Solution:
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        i = m - 1
        j = n - 1
        res_index = m + n - 1
        while(i >= 0 and j >= 0):
            if nums1[i] >= nums2[j]:
                nums1[res_index] = nums1[i]
                i -= 1
                res_index -= 1
            elif nums1[i] < nums2[j]:
                nums1[res_index] = nums2[j]
                j -= 1
                res_index -= 1
        while(j >= 0):
            nums1[res_index] = nums2[j]
            j -= 1
            res_index -= 1

感悟:
对于这种类型的题目，感觉使用while循环要优于for循环，因为比较好控制。