以 Python 合併排序陣列

假設我們有二個排好序的陣列 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
  • 當 end >= 0 並且不為 A[end]，
    • end := end – 1
  • 當 j < B 的長度時
    • 如果 i > end 並且不為 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
  • 當 num_arr [j] 不為 0 時，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]

更新於：28-APR-2020

2K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告