day17 题目：剑指 Offer 40. 最小的 k 个数、剑指 Offer 41. 数据流中的中位数

知识点：数组、设计、排序、双指针，难度为简单、困难

学习计划链接：「剑指 Offer」 - 学习计划

剑指 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

思路及代码

思路 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()
 */