สมมติว่ามีรายการที่เรียงแล้วสองรายการ 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]
ขั้นตอนการแก้ปัญหา
- x := รายการใหม่
- i := 0, j := 0
- while i < len(lst0) และ j < len(lst1)
- ถ้า lst0[i] > lst1[j] ใส่ lst1[j] เข้า x, j += 1
- ถ้า lst0[i] < lst1[j] ใส่ lst0[i] เข้า x, i += 1
- มิฉะนั้น ใส่ lst0[i] และ lst1[j] เข้า x, i += 1, j += 1
- while i < len(lst0) ใส่ lst0[i] เข้า x, i += 1
- while j < len(lst1) ใส่ lst1[j] เข้า x, j += 1
- คืนค่า x
ตัวอย่างโค้ด
class Solution:
def solve(self, lst0, lst1):
x = []
i = 0
j = 0
while i < len(lst0) and j < len(lst1):
if lst0[i] > lst1[j]:
x.append(lst1[j])
j += 1
elif lst0[i] < lst1[j]:
x.append(lst0[i])
i += 1
else:
x.append(lst0[i])
x.append(lst1[j])
i += 1
j += 1
while i < len(lst0):
x.append(lst0[i])
i += 1
while j < len(lst1):
x.append(lst1[j])
j += 1
return x
ob = Solution()
print(ob.solve([1,2,4,7], [1,3,4,5,6,8]))
อินพุต
[1,2,4,7], [1,3,4,5,6,8]
เอาต์พุต
[1, 1, 2, 3, 4, 4, 5, 6, 7, 8]
