leetcode 88 合并两个有序数组

方法:双指针 / 从后往前

  • 时间复杂度 : O(n + m)
  • 空间复杂度 : O(1)
class Solution(object):
    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.
        """
        p1 = m - 1
        p2 = n - 1
        p = m + n - 1

        while p1 >= 0 and p2 >= 0:
            if nums1[p1] < nums2[p2]:
                nums1[p] = nums2[p2]
                p2 -= 1
            else:
                nums1[p] =  nums1[p1]
                p1 -= 1
            p -= 1
        nums1[:p2+1]=nums2[:p2+1]

官方题解https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetcode/已经说的很好了

我只补充

 nums1[:p2+1]=nums2[:p2+1]

因为从后往前遍历

有可能num1已经遍历完了,num2还没有,这是个需要把num2最前面剩下的数字都放到num1的最前面去(因为都比num1最小的数字还要小),所以直接把这一段放过去(num1已经遍历完了)

那么num2没遍历完呢:那理论上就不需要任何操作,因为num1的元素已经在正确的位置了,而这个时候p2会是-1

发表评论