第 17 天
排序（中等）
剑指 Offer 40. 最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：
输入：arr = [0,1,2,1], k = 1
输出：[0]
限制：
0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
解题思路：直接排序、堆、二叉排序树、快速查找
直接排序：直接调用sort方法排序，输入前k个即可。显然不算一个好方法
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] res = new int[k];
Arrays.sort(arr);
if (k >= 0) {
System.arraycopy(arr, 0, res, 0, k);
}
return res;
}
}
复杂度：时间 O(nlogn) 空间 O(logn)
堆：利用大根堆结构的性质，Java集合框架中已有 PriorityQueue 结构，建一个容量为 k 的堆，先添加 k 个数，然后每次弹出队列中最大的数，堆中保留的就是前 k 小的数
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] res = new int[k];
if (k == 0) {
return res;
}
PriorityQueue<Integer> queue = new PriorityQueue<>((v1, v2) -> v2 - v1);
for (int i = 0; i < k; i ++) {
queue.add(arr[i]);
}
for (int i = k; i < arr.length; i ++) {
if (queue.peek() > arr[i]) {
queue.poll();
queue.add(arr[i]);
}
}
for (int i = 0; i < k; i ++) {
res[i] = queue.poll();
}
return res;
}
}
复杂度：时间 O(nlogk) 空间 O(k)
二叉排序树：利用 TreeMap 结构中元素的有序性，TreeMap的key 是数字，value 是该数字的个数。遍历数组中的数字，维护一个数字总个数为 K 的 TreeMap，而后与大根堆操作类似，先添加 K 个元素，然后每次比较新来数字与 TreeMap 中最大数字的大小，保证 TreeMap 中是最小的 K 个数
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int[] res = new int[k];
if (k == 0) {
return res;
}
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
for (int i = 0; i < k; i ++) {
treeMap.put(arr[i], treeMap.getOrDefault(arr[i], 0) + 1);
}
for (int i = k; i < arr.length; i ++) {
// k个中最大的元素及它的个数
Map.Entry<Integer, Integer> entry = treeMap.lastEntry();
if (entry.getKey() > arr[i]) {
treeMap.put(arr[i], treeMap.getOrDefault(arr[i], 0) + 1);
if (entry.getValue() == 1) {
treeMap.pollLastEntry();
}
else {
treeMap.put(entry.getKey(), entry.getValue() - 1);
}
}
}
int idx = 0;
for (Map.Entry<Integer, Integer> entry: treeMap.entrySet()) {
int temp = entry.getValue();
while (temp -- > 0) {
res[idx ++] = entry.getKey();
}
}
return res;
}
}
复杂度：时间 O(nlogk) 空间 O(k)
快速查找：直接通过快排思想切分排好第 K 小的数，那么它左边的数就是比它小的另外 K-1 个数，套用快排模板完成查找
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0 || arr.length == 0) {
return new int[0];
}
// 最后一个参数表示我们要找的是下标为k-1的数
return quickSearch(arr, 0, arr.length - 1, k - 1);
}
private int[] quickSearch(int[] nums, int lo, int hi, int k) {
// 每快排切分1次，找到排序后下标为j的元素，如果j恰好等于k就返回j以及j左边所有的数；
int j = partition(nums, lo, hi);
if (j == k) {
return Arrays.copyOf(nums, j + 1);
}
// 否则根据下标j与k的大小关系来决定继续切分左段还是右段。
return j > k? quickSearch(nums, lo, j - 1, k): quickSearch(nums, j + 1, hi, k);
}
// 快排切分，返回下标j，使得比nums[j]小的数都在j的左边，比nums[j]大的数都在j的右边。
private int partition(int[] nums, int lo, int hi) {
int v = nums[lo];
int i = lo, j = hi + 1;
while (true) {
while (++i <= hi && nums[i] < v);
while (--j >= lo && nums[j] > v);
if (i >= j) {
break;
}
int t = nums[j];
nums[j] = nums[i];
nums[i] = t;
}
nums[lo] = nums[j];
nums[j] = v;
return j;
}
}
复杂度：时间 O(n) 空间 O(logn)
剑指 Offer 41. 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1：
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2：
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
限制：
最多会对 addNum、findMedian 进行 50000 次调用。
解题思路：数组排序（超时）、二分查找、双堆
双堆：利用一个大根堆和一个小根堆分别存放一半的元素，大根堆存放小元素，小根堆存放大元素，此时大根堆的堆顶与小根堆的堆顶刚好可以算出中位数
class MedianFinder {
PriorityQueue<Integer> smallHeap, bigHeap;
public MedianFinder () {
bigHeap = new PriorityQueue<>((n1, n2) -> n2-n1);
smallHeap = new PriorityQueue<>((n1, n2) -> n1-n2);
}
// 当元素为偶数数量时，两堆顶/2即为中间数
// 当元素为奇位数量时，选一个堆顶作为中间数存放（此题解选小顶堆）
public void addNum(int num) {
// (1)说明相差>1，调整平衡性。向smallHeap添加元素达到平衡
if (bigHeap.size() != smallHeap.size()) {
if (bigHeap.peek() > num) {
smallHeap.offer(bigHeap.poll());
bigHeap.offer(num);
}
else {
smallHeap.offer(num);
}
}
// (2)完全平衡(平衡性为0)时。选择一个堆作为中间数存放。这里选的是bigHeap，所以当平衡时优先往bigHeap存
else {
// 符合性质，直接push达到平衡性
if (bigHeap.isEmpty() || smallHeap.peek() > num) {
bigHeap.offer(num);
}
// 不符合性质，对调位置
else {
bigHeap.offer(smallHeap.poll());
smallHeap.offer(num);
}
}
}
public double findMedian() {
if (bigHeap.size() == smallHeap.size()) {
return ((double) bigHeap.peek() + smallHeap.peek()) / 2;
}
else {
return bigHeap.peek();
}
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
