Introduction
Priority Queue https://www.youtube.com/watch?v=t0Cq6tVNRBA&list=PLUL4IRMCZfeXjd5AzDyry39Mf_pn1YLjQ
Time Complexity
Find min/max: O(1)
Delete min/max: O(log(n))
Insert: O(log(n))
Implementation Python Queue
: https://docs.python.org/3/library/queue.html#queue.PriorityQueue
1 2 3 4 5 6
from Queue import PriorityQueueq = PriorityQueue() q.put((1 , item)) q.put((2 , item2)) q.get()
Python heapq
: https://docs.python.org/2/library/heapq.html (use a priority queue to implemented a min heap )
1 2 3 4 5 6
from heapq import *heap = [] heappush(heap, item) heappop(heap) heappushpop(heap, item)
347. Top K Frequent Elements
Leetcode: https://leetcode.com/problems/top-k-frequent-elements/description/
[Solution] Build a hashmap to record the frequency of numbers, and use MaxHeap to sort the elements in the HashMap
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
class { public List<Integer> topKFrequent (int [] nums, int k) { Map<Integer, Integer> dict = constructHashMap(nums); PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(dict.size(), new Comparator<Map.Entry<Integer, Integer>>() { public int compare (Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b) { return b.getValue() - a.getValue(); } } ); for (Map.Entry<Integer, Integer> entry: dict.entrySet()) { pq.offer(entry); } List<Integer> res = new ArrayList<Integer>(); for (int i = 0 ; i < k; i++) { Map.Entry<Integer, Integer> top = pq.poll(); res.add(top.getKey()); } return res; } private Map<Integer, Integer> constructHashMap (int [] nums) { Map<Integer, Integer> res = new HashMap<Integer, Integer>(); for (int num: nums) { Integer cnt = res.get(num); if (cnt == null ) { res.put(num, 1 ); } else { res.put(num, cnt + 1 ); } } return res; } }
692. Top K Frequent Words
[Solution] Same as above
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
class { public List<String> topKFrequent (String[] words, int k) { Map<String, Integer> dict = count(words); PriorityQueue<Map.Entry<String,Integer>> pq = new PriorityQueue<>(dict.size(), new Comparator<Map.Entry<String, Integer>>() { public int compare (Map.Entry<String, Integer> a, Map.Entry<String, Integer>b) { if (b.getValue() == a.getValue()) { return a.getKey().compareTo(b.getKey()); } return b.getValue() - a.getValue(); } }); for (Map.Entry<String, Integer> entry: dict.entrySet()) { pq.offer(entry); } List<String> res = new ArrayList<String>(); for (int i = 0 ; i < k; i++) { res.add(pq.poll().getKey()); } return res; } private Map<String, Integer> count (String[] words) { if (words.length == 0 ) return null ; Map<String, Integer> cnt = new HashMap<String, Integer>(); for (String word : words) { Integer ch = cnt.get(word); if (ch == null ) { cnt.put(word, 1 ); } else { cnt.put(word, ch+1 ); } } return cnt; } }
[Solution]:
Use two heaps one min one max to store elements to the left of median and to the right of the median.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
from heapq import *class MedianFinder : def __init__ (self) : """ initialize your data structure here. """ self.small = [] self.big = [] def addNum (self, num: int) -> None : if len(self.small) == len(self.big): heappush(self.small, -heappushpop(self.big, -num)) else : heappush(self.big, -heappushpop(self.small, -num)) def findMedian (self) -> float: if len(self.small) == len(self.big): return (self.big[0 ] - self.small[0 ]) / 2 else : return self.small[0 ]
Use heap
to optimize sorting
23. Merge k Sorted Lists
Leetcode: https://leetcode.com/problems/merge-k-sorted-lists/
Time Complexity: _O(nlogk)_, where _k_ is the number of linked list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
from heapq import *def mergeKLists (self, lists) : head = ListNode(0 ) cur = head if not lists or len(lists) == 0 : return head.next heap = [] min_lst = lists[0 ] for lst in lists: if lst: heappush(heap, (lst.val, lst)) while heap: val, node = heappop(heap) cur.next = ListNode(val) cur = cur.next node = node.next if node: heappush(heap, (node.val, node)) return head.next
253. Meeting Rooms II
Leetcode: https://leetcode.com/problems/meeting-rooms-ii/
Solution: Use heap to optimize min
function
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
from heapq import *def minMeetingRooms (self, intervals) : """ :type intervals: List[List[int]] :rtype: int """ intervals.sort(key = lambda x: x[0 ]) if not intervals or len(intervals) == 0 : return 0 ends = [] for interval in intervals: if ends and interval[0 ] >= ends[0 ]: heappushpop(ends, interval[1 ]) else : heappush(ends, interval[1 ]) return len(ends)
近期评论