用时间换取空间的做法,用一个额外的列表去记录排好序的数组,然后再复制给NUMS1
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.
"""
nums = []
n1 = 0
n2 = 0
while n1 < m and n2 < n:
if nums1[n1] < nums2[n2]:
nums.append(nums1[n1])
n1 += 1
else:
nums.append(nums2[n2])
n2 += 1
if n1 < m:
for i in nums1[n1:m]:
nums.append(i)
if n2 < n:
for i in nums2[n2:n]:
nums.append(i)
for i in range(len(nums)):
nums1[i] = nums[i]
第二种做法是逆向思维,从后往前,已经知道m和n就知道合并后数组的最大下标,这样从后向前比较就不需要额外的空间,代码如下:
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.
"""
k = m + n - 1
n1 = m - 1
n2 = n - 1
while n1 >= 0 and n2 >= 0:
if nums1[n1] > nums2[n2]:
nums1[k] = nums1[n1]
n1 -= 1
k -= 1
else:
nums1[k] = nums2[n2]
n2 -= 1
k -= 1
if n2 >= 0:
for i in range(n2 + 1):
nums1[i] = nums2[i]