day17题目：剑指 Offer 40. 最小的k个数、剑指 Offer 41. 数据流中的中位数
知识点：数组、设计、排序、双指针，难度为简单、困难
学习计划链接：「剑指 Offer」 - 学习计划
输入整数数组 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
思路及代码
思路1：排好序后直接切片
var getLeastNumbers = function(arr, k) {
arr.sort((a, b) => a - b);
return arr.slice(0, k);
};
思路2：快排中进行统计
类似于之前题目：数组中的第K个最大元素
/**
* @param {number[]} arr
* @param {number} k
* @return {number[]}
*/
var getLeastNumbers = function(arr, k) {
function quickSort(arr, s, e) {
if(s >= e) return
let [l, r] = [s, e]
let p = arr[s]
while(l < r) {
while(l < r && arr[r] >= p) r--
while(l < r && arr[l] <= p) l++
[arr[l], arr[r]] = [arr[r], arr[l]]
}
[arr[s], arr[l]] = [arr[l], arr[s]]
if(k < l) quickSort(arr, s, l - 1)
else if(k > l) quickSort(arr, l + 1, e)
else return
}
quickSort(arr, 0, arr.length - 1)
return arr.slice(0, k)
};
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[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 次调用。
注意：本题与主站 295 题相同：https://leetcode-cn.com/problems/find-median-from-data-stream/
思路及代码
思路1：直接插入，插入时保持有序
保存至 nums 数组中，通过splice方法对其进行插入
/**
* initialize your data structure here.
*/
var MedianFinder = function() {
this.nums = []
};
/**
* @param {number} num
* @return {void}
*/
MedianFinder.prototype.addNum = function(num) {
let len = this.nums.length
if(len === 0) {
this.nums.push(num)
return
}
if(num < this.nums[0]) {
this.nums.unshift(num)
} else if(num > this.nums[len - 1]) {
this.nums.push(num)
} else {
let i = 0
while(i < len && num > this.nums[i]) ++i
this.nums.splice(i, 0, num) // 更改原数组，从i开始插入num，删除0个元素
}
};
/**
* @return {number}
*/
MedianFinder.prototype.findMedian = function() {
let len = this.nums.length
if(len === 0) return null
else if(len % 2 === 0) { // 偶数
return (this.nums[len/2-1] + this.nums[len/2]) / 2
} else return this.nums[Math.floor(len / 2)]
};
/**
* Your MedianFinder object will be instantiated and called as such:
* var obj = new MedianFinder()
* obj.addNum(num)
* var param_2 = obj.findMedian()
*/
