สมมติว่าเรามีอาร์เรย์ที่จัดเรียงอยู่สองชุด 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 และสิ้นสุด :=ความยาวของ A – 1
- ในขณะที่สิ้นสุด>=0 และไม่ใช่ A[end],
- จบ :=จบ – 1
- ในขณะที่ j <ความยาวของ B
- ถ้า i> จบและไม่ใช่ A[i] แล้ว A[i] :=B[j] และเพิ่ม j ขึ้น 1
- มิฉะนั้น ถ้า A[i]> B[j] ให้ทำ shift(A, i), A[i] :=B[j] เพิ่ม end และ j ขึ้น 1
- เพิ่ม i ขึ้น 1
วิธีการกะจะทำงานดังนี้ -
- รับอินพุต num_arr และฉัน
- j :=ความยาวของ num_arr – 1
- ในขณะที่ไม่ใช่ num_arr [j] do j :=j – 1
- ในขณะที่ 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]
