Sorting and Selection
Sorting
K-th smallest/largest
Median
Two Heaps
Overview
Find Median from Data Stream
Description
- Implement a class that can take numbers from a data stream, and can return the median of all the number it had taken
Solution
- A brute-force approach could be to maintain a sorted list.
- As with priority queue, we do not need a fully sorted structure to only find the median. We use a heap to find the max/min value of all the elements, and we can use a min heap and a max heap with the same size to find
Exercise
- Leetcode - 295. Find Median from Data Stream: link grok
TODO grok
- Leetcode - 480. Sliding Window Median: link grok
- Leetcode - 502. IPO: link grok
- Leetcode - 436. Find Right Interval: link grok
Top ‘K’ elements
Overview
数组中第 K 大的元素
TODO 优先队列
TODO 快速选择
Exercise
- Leetcode - 215. Kth Largest Element in an Array grok1 grok2
二叉搜索树中第K小的元素
Solution
- 中序遍历
- 如果需要频繁地查找第 k 小的值，记录子树的结点数
- 如果二叉搜索树经常被修改，并且需要频繁地查找第 k 小的值，使用 AVL 树
Exercise
- Leetcode - 230. Kth Smallest Element in a BST
TODO grok
- Leetcode - 973. K Closest Points to Origin link grok
- Leetcode - 1167. Minimum Cost to Connect Sticks (Premium) link grok
- Leetcode - 347. Top K Frequent Elements link grok
- Leetcode - 451. Sort Characters By Frequency link grok
- Leetcode - 703. Kth Largest Element in a Stream link grok
- Leetcode - 658. Find K Closest Elements link grok
- Leetcode - 1481. Least Number of Unique Integers after K Removals link grok
- Sum of Elements grok
- Leetcode - 767. Reorganize String link grok
- Leetcode - 358. Rearrange String k Distance Apart (Premium) link grok
- Leetcode - 621. Task Scheduler link grok
- Leetcode - 895. Maximum Frequency Stack link grok
TODO Heap Delayed Removal
- Leetcode - 480. Sliding Window Median link
- 59.1 滑动窗口的最大值 239. Sliding Window Maximum
- 59.2 队列的最大值
TODO Monotonic Queue
滑动窗口的最大值
Solution: Monotonic Queue
- 用一个双向队列来保存滑动窗口中有可能成为最大值的值
- 当滑动窗口往右移动时，队列中的数在新加入的数左端，比新加入的数先移出滑动窗口，因此如果小于新加入的数，就没有任何可能成为滑动窗口中的最大值，因此可以将这些数全部弹出
- 我们在队尾加入新元素，因为每次加入时都要保证大于等于队列中的所有元素，因此从对头到队尾满足单调递减；因此在弹出元素时可以从队尾弹出，直到队尾元素大于等于加入的数，这时队列中的全部元素也一定大于等于新加入的元素
- 每次向右移动时，也要检查移出的元素是否在队列头，如果是就要在队列头移除
- 每次移动完后，队列头的元素即为当前滑动窗口的最大值
- 时间复杂度：每次获取最大值只需要 O(1) 时间，共 O(k)。维护队列过程中，所有元素只会进队列，出队列一次，因此时间复杂度为 O(n)。总时间复杂度为 O(n) + O(k) = O(n)
Solution: Heap Delayed Removal
Exercise
- 59.1 滑动窗口的最大值 239. Sliding Window Maximum
队列的最大值
- 59.2 队列的最大值
K-way merge
Overview
合并 K 个有序链表
Description
给定 K 个有序列表， 将它们合并为一个有序链表， 返回合并后的链表
TODO 题解：优先队列
TODO 题解：分治法
Exercise
- Leetcode - 23. Merge k Sorted Lists link grok grok (find kth smallest)