สมมติว่าเรามีอาร์เรย์ที่เรียงแล้วสองอันคือ A และ B เราต้องรวมพวกมันและสร้างอาร์เรย์ที่เรียงแล้วเพียงอันเดียวคือ C ขนาดของลิสต์อาจแตกต่างกัน
ตัวอย่างเช่น สมมติ A = [1,2,4,7] และ B = [1,3,4,5,6,8] ลิสต์ที่รวมแล้ว C จะเป็น [1,1,2,3,4,4,5,6,7,8]
วิธีการแก้ปัญหา
- กำหนด i := 0, j := 0 และ end := ความยาวของ A - 1
- while end >= 0 และ not A[end]:
- end := end - 1
- while j < ความยาวของ B:
- ถ้า i > end และ not A[i] ให้ A[i] := B[j] และเพิ่ม j ขึ้น 1
- มิฉะนั้นถ้า A[i] > B[j] ให้ทำ shift(A, i), A[i] := B[j] เพิ่ม end และ j ขึ้น 1
- เพิ่ม i ขึ้น 1
เมธอด shift จะทำงานดังนี้:
- รับอินพุต num_arr และ i
- j := ความยาวของ num_arr - 1
- while not num_arr[j] ทำ j := j - 1
- while j >= i ทำ num_arr[j + 1] = num_arr[j] และ j := j - 1
ตัวอย่าง
class Solution(object):
def merge(self, nums1, m, nums2, n):
i = 0
j = 0
end = len(nums1) - 1
while end >= 0 and not nums1[end]:
end -= 1
while j < len(nums2):
if i > end and not nums1[i]:
nums1[i] = nums2[j]
j += 1
elif nums1[i] > nums2[j]:
self.shift(nums1, i)
nums1[i] = nums2[j]
end += 1
j += 1
i += 1
return nums1
def shift(self, num, i):
j = len(num) - 1
while not num[j]:
j -= 1
while j >= i:
num[j+1] = num[j]
j -= 1
ob = Solution()
print(ob.merge([1,2,3,0,0,0], 3, [2,5,6], 3))
อินพุต
[1,2,3,0,0,0] [2,5,6]
เอาต์พุต
[1, 2, 2, 3, 5, 6]
