Heap

题解

• 215 Kth Largest Element in an Array
  • O(n+klogk) time using heap sort.
  • O(nlogk) time using minimum heap.
  • Average O(n) using quick-sort-like quick-select.
  • Strict O(n) using divide & conquer.
  • O(32n) time using trie.
• 295 Find Median from Data Stream
  • O(32) insertion and O(32) query by trie.
  • O(log(n)) insertion and O(1) query by maintaining small-half maxheap and large-half minheap.
• 313 Super Ugly Number
  • O(kn) time. USACO humble number.
• 347 Top K Frequent Elements
  • O(nlog(k)) using heap.
• 355 Design Twitter
  • postTweet(userId, tweetId), getNewsFeed(userId), follow(srcId, tgtId), unfollowId(srcId, tgtId).
  • Use heap to implement getNewsFeed.
• 373 Find K Pairs with Smallest Sums
  • Given two number array, find k-th smallest pairs formed by numbers from the two arrays.
  • O(klog(k)) time by heap + BFS.
• 378 Kth Smallest Element in a Sorted Matrix
  • The matrix’s rows and columns are sorted.
  • O(nlog(n)) by binary search. O(klog(k)) by heap + BFS.
  • O(n) time algorithm presented in paper “Selection in X + Y and matrices with sorted rows and columns”, where n is number of rows.
• 407 Trapping Rain Water II
  • Given a grid with heights, find how much rain water it can trap.
  • O(mnlog(mn)) time, each time floodfill from lowest grid that cannot trap any water. The cannot-trap set is maintained by a heap.
• 630 Course Schedule III
  • Given semester days and courses with days needed and deadline, find maximum number of courses one can take in a semester.
  • Sort courses by deadline, use max-heap (days) to maintain optimal choice. Replace heap top when there is a course taking less time than top.
• 692 Top K Frequent Words