最小的k个数

Esay 原题连接：最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
输入：arr = [0,1,2,1], k = 1
输出：[0]

限制：

  1. 0 <= k <= arr.length <= 10000

  2. 0 <= arr[i] <= 10000

解题思路

排序输出前k位，取决于你希望使用哪一种算法实现排序，有现成的自然是最快的

Java代码

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] ans = new int[k];
        Arrays.sort(arr);
        for(int i=0; i<k; i++){
            ans[i] = arr[i];
        }
        return ans;
    }
}

数据流中的中位数

hard 原题连接：数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。

示例：

输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
输入：
["MedianFinder","addNum","findMedian","addNum","findMedian"]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

提示：

  1. 最多会对 addNum、findMedian 进行 50000 次调用。

解题思路

取中位数的值，根据题目要求，添加和分析中位数都会有50000次以内的调用，需要尽可能的降低添加和搜索的时间复杂度

单一数据结构如ArrayList，LinkedList做存储的话，在添加或搜索的复杂度上会过大 O( n )，在此使用优先队列PriorityQueue对两边分别排序则效果更好

PriorityQueue进行add的复杂度是O( logn )，弹出堆顶是常熟复杂度，自然是首选。

那么如何分配两边的值呢？（当新添加一个值时，是放前堆还是后堆）

因为使用堆的目的是维护两端长度一致，便于我们peek输出中位数，所以分配的前提是两端长度相等

其次，因为是依次添加数据，所以其实新数据添加至前端还是后端都可以，要保证两部分都是排序过的数据

排序过后，两个堆顶作为交流的通道，传递顶值，这样就会有最大堆的最小值放入最小堆，最小堆的最大值防入最大堆

因为数据是依次放入的，整个部分除去中位数的部分就都是顺序排序的，而偶数时的中位数是取中间值，不论顺序相加除2即可

当位奇数位时，新添加值会与两个中位数对比后返回

Java代码

class MedianFinder {

    /** initialize your data structure here. */
     Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，顺序排列，保存较大的一半，弹出最小
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，逆序排列，保存较小的一半，弹出最大
    }
    public void addNum(int num) {
        if(A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

其实我也没有想到PriorityQueue，不过类似的使用了堆和对应的堆排序

以下是我的代码，但是用例超时…

class MedianFinder {

    /** initialize your data structure here. */
     Stack<Integer> A, B;
    public MedianFinder() {
        A = new Stack<>(); // 顺序排列，保存较大的一半，弹出最小
        B = new Stack<>(); // 逆序排列，保存较小的一半，弹出最大
    }
    public void addNum(int num) {
        if(A.size() != B.size()) {
            sortBigStack(A,num);
            sortSmlStack(B,A.pop());
        } else {
            sortSmlStack(B,num);
            sortBigStack(A,B.pop());
        }
    }
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }

    public void sortBigStack(Stack<Integer> stack, int a) {
        Stack<Integer> midStack = new Stack<>();
        while(!stack.isEmpty() && stack.peek() > a) {
            midStack.push(stack.pop());
        }
        stack.push(a);
        while(!midStack.isEmpty()){
            stack.push(midStack.pop());
        }
    }

        public void sortSmlStack(Stack<Integer> stack, int a) {
        Stack<Integer> midStack = new Stack<>();
        while(!stack.isEmpty() && stack.peek() < a) {
            midStack.push(stack.pop());
        }
        stack.push(a);
        while(!midStack.isEmpty()){
            stack.push(midStack.pop());
        }
    }
}