day17 题目：剑指 Offer 40. 最小的 k 个数、剑指 Offer 41. 数据流中的中位数
知识点：数组、设计、排序、双指针，难度为简单、困难
学习计划链接：「剑指 Offer」 - 学习计划
| 题目 | 知识点 | 难度 |
|---|---|---|
| 剑指 Offer 40. 最小 的 k 个数 | 数组、分治、快速选择、排序、堆（优先队列） | 简单 |
| 剑指 Offer 41. 数据流中的中位数 | 设计、双指针、数据流排序 | 困难 |
# 剑指 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 <= 100000 <= arr[i] <= 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) | |
}; |
# 剑指 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次调用。
注意：本题与主站 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() | |
*/ |
