以 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+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告