剑指 Offer 40. 最小的k个数 & 41. 数据流中的中位数

40题目描述：

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

解析：

1.库函数,首先把数组arr排序，定义一个新的数组res，数组的长度为k
2.遍历循环数组arr，把前k个数赋值到数组res
3.最后返回数组res即可

Java:

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

JavaScript:

var getLeastNumbers = function(arr, k) {
    arr = arr.sort((a, b) => a - b);
    let res = [];
    for(let i = 0; i < k; i++) {
        res[i] = arr[i];
    }
    return res;
};

41题目描述：

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

例如，

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

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

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

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

解析：

用大顶堆+小顶堆方法，可以看作大顶堆是普通班，小顶堆是实验班。数量上时刻保持小顶-大顶<=1（两堆相等或者小顶比大顶多一个）。
新学生先入普通班（大顶堆），此时可能会失去平衡了，于是取大顶堆的第一个（班里最好的学生）加入实验班（小顶堆），判断若数量过多（不是等于或多一个），取第一个（实验班里最差的学生）到普通班（大顶堆）里。取中位数的时候，若两堆数量相等，则各取堆顶取平均，若小顶比大顶多一，则多的那一个就是中位数。

Java:

class MedianFinder {
    PriorityQueue<Integer> right;
    PriorityQueue<Integer> left;
    /** initialize your data structure here. */
    public MedianFinder() {
        left = new PriorityQueue<>((n1, n2) -> n2 - n1);
        right = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        left.add(num);
        right.add(left.poll());
        if(left.size() + 1 < right.size()) {
            left.add(right.poll());
        }
    }
    
    public double findMedian() {
        if(right.size() > left.size()) {
            return right.peek();
        }
        return (double)(left.peek() + right.peek()) / 2;
    }
}

JavaScript:

var MedianFinder = function() {
    this.arr = [];
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function(num) {
    this.arr.push(num);
    this.arr.sort((a, b) => {
        return a - b;
    })
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function() {
    let length = this.arr.length;
    let mid = Math.floor(length / 2);
    if(length === 0) {
        return 0;
    } else if(length % 2 === 0) {
        return (this.arr[mid - 1] + this.arr[mid]) / 2;
    } else {
        return this.arr[mid];
    }
};