정렬된 배열 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의 길이 정의
- 종료 중>=0이고 A[종료]가 아님,
- 끝 :=끝 – 1
- while j
- 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]가 아닌 동안 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]