在 Python 中合并排序数组

pythonserver side programmingprogramming更新于 2025/10/31 20:28:17

假设我们有两个排序数组 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]

要解决此问题，请按照以下步骤 −

define i := 0, j := 0 and end := length of A – 1
while end >= 0 and not A[end],
- end := end – 1
当 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
当 not num_arr [j] 时执行 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))