合并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，结束：= A – 1的长度

• 而end> = 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

• 使我增加1

shift方法将如下所示工作-

• 接受输入num_arr，然后我

• j：= num_arr的长度– 1

• 而不是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))

输入项

[1,2,3,0,0,0]
[2,5,6]

输出结果

[1, 2, 2, 3, 5, 6]