leetcode-python-优先级队列与时间复杂度
leetcode-python-專欄目錄
專題概述
無
目錄
無
代碼相關
最后
如果覺得本文對你有幫助，為我收藏點贊，若文中有任何問題（哪步算法沒看懂，或者涉及到的python語法不了解，或者哪里出錯了）可在評論區留言。
本文的內容
本文圍繞leetcode-347展開，先用最少量的代碼（collections.Counter）解決問題，然后根據Counter的源碼找到該算法的時間復雜度。由此引入優先級隊列，介紹python中優先級隊列的用法，最后用兩個不同的優先級隊列解決本題。
熟悉了優先隊列之后，通過leetcode-23來實戰。
Leetcode347號問題-前K個高頻元素
題目鏈接
代碼思路：
代碼實現：
def topKFrequent(self, nums, k):from collections import Counterreturn [c[0] for c in Counter(nums).most_common(k)]雖然本道題目完成了，但是我們想深究下內部的時間復雜度。
most_common()源碼分析
我們發現了heapq.nlargest這個python內置的堆的方法。
def most_common(self, n=None):if n is None:return sorted(self.items(), key=_itemgetter(1), reverse=True)# 堆的使用，也就是優先級return _heapq.nlargest(n, self.items(), key=_itemgetter(1))再繼續看heapq.nlargest源碼。
def nlargest(n, iterable, key=None):"""Find the n largest elements in a dataset. Equivalent to: sorted(iterable, key=key, reverse=True)[:n] """注釋中告訴我們這個方法約等于sorted方法，我們假設python內置的sorted就是普通的快排（不考慮內部的優化），那么他的時間復雜度就是O(nlogn)
使用most_common時，即使是我們只想獲得頻率最大的一個，也需要排序整個數組。消耗O(nlogn)的時間復雜度
這時為了降低時間復雜度我們就需要優先級隊列了。
python中的優先級隊列
在python中優先級隊列也是在堆的基礎上進行了一層封裝。(from queue import PriorityQueue)
詳情請看：
dyq666：日常編程中的python-優先級隊列使用優先級隊列
在使用前需要先搞清楚優先級隊列的時間復雜度，往一個長度為n的優先級隊列中插入一個元素時間復雜度是O(logn)。那么把n個元素插入一個空的優先級隊列中時間復雜度就為O(nlogn)。
如果把n個元素插入一個空的優先級隊列中，但是優先級隊列的最大長度為k，那么時間復雜度就為O(nlogk)。
基于這個時間復雜度的計算方式，在這道題中可以構造出兩種優先級隊列。隊列一保存所有頻率最大的元素，也就是長度為k。隊列二保存所有頻率最小的元素，也就是長度為（n-k）。這兩種方式哪種更好，也就取決于n與k大小之間的差距了。
（一）優先級隊列保存頻率大的元素
題目分析：
先使用Counter統計頻率，然后維護一個優先級隊列，這個隊列總共只能存k個元素（ 當前頻率最高的k各元素 ），也就是優先級越高代表他的頻率越高。
遍歷整個Counter，入隊到k個元素。隊滿之后，每次都把隊列中優先級最小的元素與當前元素對比，選擇優先級大的一個。
遍歷結束后，整個隊列就是結果了。
在這里最重要的就是想明白你把什么當做優先級，因為每次出隊的都是優先級最小的，我們不想要頻率小的，所以我們讓頻率越小的優先級越低。
代碼思路：
時間復雜度：O(nlogk)
1. 統計頻率，counter算是一個dict，key是數，value是對應的頻率
2. 如果k跟所有數相同就直接返回所有數
3. 創建優先隊列，設置優先隊列的最大長度（這里最大長度是k）。
4. 遍歷所有數和它的頻率。這里的優先級與頻率相同。
5. 如果當前隊列長度小于最大長度，直接入隊
6. 如果等于最大長度了，并且當前的優先級(-freq)比隊列中優先級最低的元素優先級高(第一個元素)。
那么把優先級最低的出隊列，當前的入隊列
7. 返回優先級隊列中所有的數
代碼實現：(注釋中標明了代碼思路中步驟的序號)
def topKFrequent02(self, nums, k):# 步驟一from collections import Countercounter = Counter(nums)len_counter = len(counter)# 步驟二if len_counter == k:return list(counter.keys())# 步驟三from queue import PriorityQueue as PQpq, max_len = PQ(), k# 步驟四for num, freq in counter.items():# 步驟五if len(pq.queue) < max_len:pq.put((freq, num))# 步驟六elif freq > pq.queue[0][0]:pq.get()pq.put((freq, num))# 步驟七return [p[-1] for p in pq.queue]（二）優先級隊列保存頻率小的元素
區別分析：
Leetcode23號問題-合并K個排序鏈表
題目鏈接
題目分析：
總共有n個降序的鏈表，意味著每個鏈表當前的頭結點都是最小的，所以只需要維護一個大小為n的優先級隊列，每次出隊后，出隊的內條鏈表的頭結點，如果不是最后一個節點，就將它的下一個節點入隊。
舉個例子：[1->2->6, 2->3, 3->4->5]。第一步1,2,和3入隊，然后1出隊，1的下一個節點2入隊。這種方式保證了最終合成的鏈表一定是排好序的，因為一條鏈表不能有兩個節點同時在隊列中，這是沒有意義的，因為一條鏈表上前面節點的一定是更小的或者是相等。
基于上述的講解，我們只需要把整個優先級隊列都出完就結束了
代碼思路：
1. queue_index的作用：假設兩個元素的優先級相同，那么將會去比較元組中第二個值。
但是第二個值如果是一個類的實例，可能沒重寫比較的方法，所以需要一個可以比較的輔助變量來區分。（這部分一定要仔細閱讀，或者嘗試幾個例子，或者去文章提到的優先級隊列詳情的文章中去看看）
2. 初始化隊列，將所有鏈表的頭結點入隊
3. 創建最終結果鏈表的虛擬頭結點
4. 每次從隊列中獲取優先級最小的元素，用needle去穿針引線
5. 如果該節點后面還有節點，就將后面的一個節點入隊
代碼實現：
def mergeKLists(self, lists):from queue import PriorityQueue as PQpq = PQ()# 步驟一queue_index = 0# 步驟二for node in lists:if node:pq.put((node.val, queue_index, node))queue_index += 1# 步驟三dummy = ListNode(None)needle = dummy# 步驟四while pq.queue:node = pq.get()[-1]needle.next = nodeneedle = needle.next# 步驟五if node.next:pq.put((node.next.val, queue_index, node.next))queue_index += 1return dummy.next總結
總結
以上是生活随笔為你收集整理的leetcode-python-优先级队列与时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 深度学习笔记：手写一个单隐层的神经网络
- 下一篇： 深度学习表征的不合理有效性——从头开始构