ソートされた配列をPythonでマージ

2つの並べ替えられた配列AとBがあるとします。それらをマージして、1つの並べ替えられた配列Cのみを形成する必要があります。リストのサイズは異なる場合があります。

たとえば、A=[1,2,4,7]およびB=[1,3,4,5,6,8]とすると、マージされたリストCは[1,1,2,3,4、 4,5,6,7,8]

これを解決するには、次の手順に従います-

• ifine i：=0、j：=0 and end：=length of A – 1
• while end> =0であり、A[end]ではありません。
  • end：=end – 1
• whilej
• 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を取得し、i
• 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]