題目
給定兩個按 非遞減順序 排列的整數(shù)列表 nums1 和 nums2，另再給定兩個整數(shù) m 和 n涉枫，其中 nums1 的長度為 m + n ， nums2 的長度為 n 腐螟，列表 nums1 中最后 n 個元素均為默認值 0 愿汰。
請合并 nums2 到 nums1 中，使合并后的列表 nums1 同樣按 非遞減順序 排列乐纸。
注意： nums1 中最后 n 個默認值0不用于合并衬廷，應(yīng)忽略。同時只允許在原列表 nums1 上操作汽绢，而不能返回一個新創(chuàng)建的列表吗跋。
例如：
給定數(shù)據(jù)：nums1 = [1, 2, 4, 0, 0, 0]，m = 3庶喜，nums2 = [-2, 3, 6]小腊，n = 3
返回結(jié)果：[-2, 1, 2, 3, 4, 6]說明：需要合并的分別為 [1, 2, 4] 和 [-2, 3, 6] 。
給定數(shù)據(jù)：nums1 = [0]久窟，m = 0秩冈，nums2 = [-2]，n = 1
返回結(jié)果：[-2]說明：需要合并的分別為 [] 和 [-2] 斥扛。
實現(xiàn)思路1
- 直接合并然后進行排序
- 遍歷 nums2 入问，將 nums2 的元素放入到 nums1 的后 n 個元素中，最后對 nums1 進行排序即可
代碼實現(xiàn)
def merge(nums1, m, nums2, n):
nums1[m:] = nums2
nums1.sort()
return nums1
上面我們直接使用了Python的
sort()函數(shù)來進行排序稀颁，但如果在常見面試中芬失，一般是不允許直接使用Python的內(nèi)置函數(shù)來處理，這時候可以使用常見的排序算法匾灶，如快速排序來進行處理棱烂，但其時間復(fù)雜度為O((m+n)log(m+n))，那么本題有沒有更好的解決辦法呢阶女？接下來颊糜，我們將介紹另一種
雙指針方法來處理，其時間復(fù)雜度是O(m+n)秃踩。
實現(xiàn)思路2
- 定義3個值：index1衬鱼、index2、tmp_index
- 其中 index1 表示 nums1 中用于合并元素的下標憔杨，初始值為 m - 1鸟赫； index2 表示 nums2 中用于合并元素的下標，初始值為 n - 1；tmp_index 表示 nums1 中所有元素的下標抛蚤，初始值為 m + n - 1
- 使用
while循環(huán)台谢，每次循環(huán)把 nums1 和 nums2 所有待合并的元素中的最大值取出來，放到 nums1 中的 tmp_index 下標位置 - 如果 nums1和nums2 其中一方的待合并元素都排序完了霉颠，那么直接把另一方的剩余元素全部放到nums1对碌，最后直接跳出循環(huán)即可
代碼實現(xiàn)
def merge(nums1, m, nums2, n):
index1, index2 = m - 1, n - 1
tmp_index = m + n - 1
while index1 >= 0 or index2 >= 0:
if index1 == -1:
nums1[:tmp_index+1] = nums2[:index2+1]
break
elif index2 == -1:
nums1[:tmp_index+1] = nums1[:index1+1]
break
elif nums1[index1] <= nums2[index2]:
nums1[tmp_index] = nums2[index2]
index2 -= 1
elif nums1[index1] > nums2[index2]:
nums1[tmp_index] = nums1[index1]
index1 -= 1
tmp_index -= 1
return nums1
更多Python編程題，等你來挑戰(zhàn)：Python編程題匯總（持續(xù)更新中……）
