LeetCode 스 택, 대기 열, 우선 대기 열 테마 6: 우선 대기 열 도 대기 열 입 니 다.

예제: LeetCode 347 번 문제: 앞의 K 개의 고주파 원소
전송 문: 347. 앞의 K 개 고주파 원소.
빈 정수 그룹 을 지정 하고 주파수 가 나 오기 전에 k 가 높 은 요 소 를 되 돌려 줍 니 다.
예시 1:

  : nums = [1,1,1,2,2,3], k = 2
  : [1,2]

예시 2:

  : nums = [1], k = 1
  : [1]

설명:
4. 567917. 주어진 k 가 항상 합 리 적 이 고 1 ≤ k ≤ 배열 에서 서로 다른 요소 의 개 수 를 가정 할 수 있 습 니 다
4. 567917. 당신 의 알고리즘 은 시간 복잡 도가 O (n log n) 보다 높 아야 합 니 다. n 은 배열 의 크기 입 니 다
분석: "당신 의 알고리즘 은 시간 복잡 도가 O (n log n) 보다 높 아야 합 니 다. n 은 배열 의 크기 입 니 다."이것 은 문제 가 우리 에 대한 요구 입 니 다. 우리 가 쉽게 생각 할 수 있 는 사고방식 은 counter 이후 의 데 이 터 를 value 에 대해 정렬 하 는 것 입 니 다. 그러나 가장 좋 은 정렬 알고리즘 이라도 시간의 복잡 도 는 다시 말 하면 문 제 는 우리 가 정렬 알고리즘 을 사용 할 수 없 도록 제한 합 니 다.그러면 앞의 k 와 같은 문제 에 대해 자 연 스 러 운 사고방식 은 바로 우선 대기 열 을 사용 하 는 것 이다. 이 점 을 생각하면 이 문 제 는 일반적인 문제 이다.
Python 코드:

class Solution:
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        import heapq
        import collections

        #      
        l = []

        wordcount = collections.defaultdict(int)
        for num in nums:
            wordcount[num] += 1

        for key, val in wordcount.items():
            heapq.heappush(l, (-val, key))
        res = []
        for _ in range(k):
            _, key = heapq.heappop(l)
            res.append(key)
        return res

연습: LeetCode 23 번 문제: K 개 정렬 링크 통합
전송 문: 23. K 개의 정렬 링크 를 합 칩 니 다.
k 개의 정렬 링크 를 합 쳐 합 친 정렬 링크 를 되 돌려 줍 니 다.알고리즘 의 복잡 도 를 분석 하고 설명 하 십시오.
예시:

  :
[
 1->4->5,
 1->3->4,
 2->6
]
  : 1->1->2->3->4->4->5->6

사고방식 1: 우선 대기 열 을 사용 합 니 다.이것 은 교과서 의 예제 와 유사 한 문제 다.여기 서 우 리 는 생활 속 의 예 를 들 어 사고 방향 을 이해 하 는데 사실은 조금도 어렵 지 않다.
만약 에 다음 과 같은 생활 상황 이 있다 고 가정 합 니 다. 만약 에 당신 이 체육 선생님 이 고 3 개 반 의 학생 이 있다 고 가정 하면 그들 은 키 에 따라 키 가 작 을 때 부터 높 을 때 까지 3 열 종대 로 줄 을 섰 습 니 다. 지금 은 이 3 개 반 의 학생 들 도 키 에 따라 키 가 작 을 때 부터 높 을 때 까지 한 열 종대 로 배열 해 야 합 니 다.
우 리 는 이렇게 할 수 있다.
1. 3 개 반 의 학생 들 로 하여 금 열 에 따라 당신 앞 에 서 게 합 니 다. 이때 당신 은 팀 의 선두 에 서 있 는 학생 들 의 온몸 을 볼 수 있 고 나머지 학생 들 은 앞의 친구 들보 다 머리 가 높 은 부분 만 볼 수 있 습 니 다.
2. 각 팀 의 첫 번 째 학생 3 명 은 가장 작은 학생 을 '팀 4' (즉, 우 리 는 최종 적 으로 순 서 를 잘 배열 했다 고 생각 하 는 대열) 에 올 려 주 십시오. 이 열 에 있 는 다음 학생 은 한 걸음 앞으로 나 아 갑 니 다.
3. 두 번 째 단 계 를 반복 해서 3 개 반 의 학생 들 이 모두 출석 할 때 까지 합 니 다.
Python 2 코드: 주의: 아래 코드 는 Python 2 에서 통과 할 수 있 습 니 다. Python 3 의 hepq 는 사용자 정의 대상 에 들 어 가 는 것 을 지원 하지 않 지만 커 브 를 돌려 서 색인 번 호 를 전달 하면 됩 니 다.

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        import heapq
        l = []
        for head in lists:
            if head:
                heapq.heappush(l, (head.val, head))
        dummy_node = ListNode(-1)
        cur = dummy_node

        while l:
            _, head = heapq.heappop(l)
            cur.next = head
            cur = cur.next
            if head.next:
                heapq.heappush(l, (head.next.val, head.next))

        return dummy_node.next

Python 3 코드:

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        import heapq
        l = []
        size = len(lists)

        for index in range(size):
            if lists[index]:
                heapq.heappush(l, (lists[index].val, index))

        dummy_node = ListNode(-1)
        cur = dummy_node

        while l:
            _, index = heapq.heappop(l)

            head = lists[index]

            cur.next = head
            cur = cur.next
            if head.next:
                heapq.heappush(l, (head.next.val, index))
                lists[index] = head.next
                head.next = None

        return dummy_node.next

사고 2: 분 치.또한 병합 정렬 의 분할 사상 으로 해결 할 수 있 고 코드 구조 와 병합 정렬 은 똑같다 고 할 수 있다.
1. 먼저 이 문 제 를 둘 로 나 누 어 해결 했다.
2. 어떻게 합병 할 것 인 가 를 다시 고려 하 는 과정 도 재 귀 방법 이다.
Python 코드:

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """

        size = len(lists)
        if size == 0:
            return None
        return self.__merge_k_lists(lists, 0, size - 1)

    def __merge_k_lists(self, lists, left, right):
        if left >= right:
            return lists[left]
        mid = left + (right - left) // 2
        listnode1 = self.__merge_k_lists(lists, left, mid)
        listnode2 = self.__merge_k_lists(lists, mid + 1, right)
        return self.__merge_two_sorted_list_node(listnode1, listnode2)

    def __merge_two_sorted_list_node(self, list1, list2):
        if list1 is None:
            return list2
        if list2 is None:
            return list1

        if list1.val < list2.val:
            list1.next = self.__merge_two_sorted_list_node(list1.next, list2)
            return list1
        else:
            list2.next = self.__merge_two_sorted_list_node(list1, list2.next)
            return list2

(이 절 완료)