Python에서 K 정렬 목록을 병합하는 프로그램

어떤 목록이 있다고 가정하고 이 목록은 정렬됩니다. 이 목록을 하나의 목록으로 병합해야 합니다. 이를 해결하기 위해 힙 데이터 구조를 사용합니다. 따라서 목록이 [1,4,5], [1,3,4], [2,6]이면 최종 목록은 [1,1,2,3,4,4,5,6]이 됩니다. .

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=목록 크기
• 힙 :=새 목록
• 각 인덱스 i와 목록의 행[i]에 대해 다음을 수행합니다.
  • 행이 비어 있지 않으면
    • 힙에 (행[0], i, 0) 삽입
• res :=새 목록
• 힙이 비어 있지 않은 동안 수행
  • num, row, col :=힙의 최상위 요소
  • res 끝에 숫자 삽입
  • 열 <목록의 크기[행] - 1이면
    • 힙에 목록[row, col + 1], row, col + 1 삽입
• 반환 결과

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

import heapq
class Solution:
   def solve(self, lists):
      n = len(lists)
      heap = []
      for i, row in enumerate(lists):
         if row:
            heapq.heappush(heap, (row[0], i, 0))
         res = []
         while heap:
            num, row, col = heapq.heappop(heap)
            res.append(num)
         if col < len(lists[row]) - 1:
            heapq.heappush(heap, (lists[row][col + 1], row, col + 1))
      return res
ob = Solution()
lists = [[],[],[11, 13],[],[4, 4, 14],[4],[11],[1, 8]]
print(ob.solve(lists))

입력

[[],[],[11, 13],[],[4, 4, 14],[4],[11],[1, 8]]

출력

[1, 4, 4, 4, 8, 11, 11, 13, 14]