703.数据流中的第 K 大元素

703.数据流中的第 K 大元素

Category	Difficulty	Likes	Dislikes
algorithms	Easy (52.28%)	380	-

Tags
Companies
设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。
请实现 KthLargest 类：

• KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
• int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

示例：
输入： [“KthLargest”, “add”, “add”, “add”, “add”, “add”] [[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]] 输出： [null, 4, 5, 5, 8, 8] 解释： KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8

提示：

• 1 <= k <= 104
• 0 <= nums.length <= 104
• -104 <= nums[i] <= 104
• -104 <= val <= 104
• 最多调用 add 方法 104 次
• 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

---

Discussion | Solution

思路

二分插入，前后需要插入 Infinity 适配最大最小的情况

解答

/*
 * @lc app=leetcode.cn id=703 lang=javascript
 *
 * [703] 数据流中的第 K 大元素
 */

// @lc code=start
/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function (k, nums) {
  this.k = k;
  this.arr = nums.sort((a, b) => +a - +b);
  this.arr.push(Infinity);
  this.arr.unshift(-Infinity);
};

/**
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function (val) {
  const findIndex = (left, right) => {
    if (left > right) return left;
    const mid = parseInt((left + right) / 2);
    const cur = this.arr[mid],
      next = this.arr[mid + 1],
      prev = this.arr[mid - 1];
    if (cur <= val && val <= next) {
      return mid;
    } else if (cur >= val && val >= prev) {
      return mid - 1;
    } else if (val > next) {
      return findIndex(mid + 1, right);
    } else if (val < prev) {
      return findIndex(left, mid - 1);
    }
  };

  const index = findIndex(0, this.arr.length - 1);

  this.arr.splice(index + 1, 0, val);

  return this.arr[this.arr.length - this.k - 1];
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * var obj = new KthLargest(k, nums)
 * var param_1 = obj.add(val)
 */
// @lc code=end