跳到主要内容

4 篇博文 含有标签「数据流」

查看所有标签

· 阅读需 3 分钟

1、题干​

设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。

例如，words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a'、'x'、'y' 和 'z' ，你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz" 与 words 中的字符串 "xyz" 匹配。

按下述要求实现 StreamChecker 类：

  • StreamChecker(String[] words) ：构造函数，用字符串数组 words 初始化数据结构。
  • boolean query(char letter)：从字符流中接收一个新字符，如果字符流中的任一非空后缀能匹配 words 中的某一字符串，返回 true ；否则，返回 false。

 

示例：

输入：
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
输出：
[null, false, false, false, true, false, true, false, false, false, false, false, true]

解释：
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // 返回 False
streamChecker.query("b"); // 返回 False
streamChecker.query("c"); // 返回n False
streamChecker.query("d"); // 返回 True ，因为 'cd' 在 words 中
streamChecker.query("e"); // 返回 False
streamChecker.query("f"); // 返回 True ，因为 'f' 在 words 中
streamChecker.query("g"); // 返回 False
streamChecker.query("h"); // 返回 False
streamChecker.query("i"); // 返回 False
streamChecker.query("j"); // 返回 False
streamChecker.query("k"); // 返回 False
streamChecker.query("l"); // 返回 True ，因为 'kl' 在 words 中

 

提示：

  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 200
  • words[i] 由小写英文字母组成
  • letter 是一个小写英文字母
  • 最多调用查询 4 * 104 次

2、思路​

  • 构造函数：字典树存储所有单词的逆序串
  • query：数组存储字符流，按字符流逆序查找字典树中是否存在该后缀

3、代码​

class StreamChecker {
    letters = [];
    trie = { end: false };

    constructor(words: string[]) {
        for (const word of words) this.add(word);
    }

    query(letter: string): boolean {
        this.letters.push(letter);
        return this.find(this.letters);
    }

    add(word: string) {
        let t = this.trie;
        for (let i = word.length - 1; i > -1; i--) {
            if (!t[word[i]]) t[word[i]] = { end: false };
            t = t[word[i]];
        }
        t.end = true;
    }

    find(letters: string[]) {
        let t = this.trie;
        for (let i = letters.length - 1; i > -1; i--) {
            t = t[letters[i]];
            if (!t) return false;
            if (t.end) return true;
        }
        return t.end;
    }
}

4、复杂度​

  • 时间复杂度：构造函数 O(mn)O(mn)，query O(mk)O(mk)，其中 n为单词数，m 为单词长度，k 为查询次数
  • 空间复杂度：O(mn+k)O(mn+k)

5、执行结果​

image.png

· 阅读需 6 分钟

1、题干​

给你两个整数 m 和 k ，以及数据流形式的若干整数。你需要实现一个数据结构，计算这个数据流的 MK 平均值 。

MK 平均值 按照如下步骤计算：

  1. 如果数据流中的整数少于 m 个，MK 平均值 为 -1 ，否则将数据流中最后 m 个元素拷贝到一个独立的容器中。
  2. 从这个容器中删除最小的 k 个数和最大的 k 个数。
  3. 计算剩余元素的平均值，并 向下取整到最近的整数 。

请你实现 MKAverage 类：

  • MKAverage(int m, int k) 用一个空的数据流和两个整数 m 和 k 初始化 MKAverage 对象。
  • void addElement(int num) 往数据流中插入一个新的元素 num 。
  • int calculateMKAverage() 对当前的数据流计算并返回 MK 平均数 ，结果需 向下取整到最近的整数 。

 

示例 1：

输入：
["MKAverage", "addElement", "addElement", "calculateMKAverage", "addElement", "calculateMKAverage", "addElement", "addElement", "addElement", "calculateMKAverage"]
[[3, 1], [3], [1], [], [10], [], [5], [5], [5], []]
输出：
[null, null, null, -1, null, 3, null, null, null, 5]

解释：
MKAverage obj = new MKAverage(3, 1); 
obj.addElement(3);        // 当前元素为 [3]
obj.addElement(1);        // 当前元素为 [3,1]
obj.calculateMKAverage(); // 返回 -1 ，因为 m = 3 ，但数据流中只有 2 个元素
obj.addElement(10);       // 当前元素为 [3,1,10]
obj.calculateMKAverage(); // 最后 3 个元素为 [3,1,10]
                          // 删除最小以及最大的 1 个元素后，容器为 [3]
                          // [3] 的平均值等于 3/1 = 3 ，故返回 3
obj.addElement(5);        // 当前元素为 [3,1,10,5]
obj.addElement(5);        // 当前元素为 [3,1,10,5,5]
obj.addElement(5);        // 当前元素为 [3,1,10,5,5,5]
obj.calculateMKAverage(); // 最后 3 个元素为 [5,5,5]
                          // 删除最小以及最大的 1 个元素后，容器为 [5]
                          // [5] 的平均值等于 5/1 = 5 ，故返回 5

 

提示：

  • 3 <= m <= 105
  • 1 <= k*2 < m
  • 1 <= num <= 105
  • addElement 与 calculateMKAverage 总操作次数不超过 105 次。

这10分真的十分难拿，临场肯定写不出来，没有第三方库肯定也写不出来

2、思路​

3棵二叉搜索树保存最近 m 个数字，其中 trees[0] 保存最小的 k 个数、trees[1] 保存中间的 m - 2*k 个数、trees[2] 保存最大的 k 个数。保存中间数字之和 sum，并在添加元素时更新，以便快速计算平均值。

addElement 时先进行移除操作，再进行插入操作：

  • 若当前已超过 m 个数，则从树中移除倒数第 m+1 个数，然后将处于后方树中最小的数字往前方的树填充
  • 将当前数字插入第一棵树，然后将前方树中多余的最大数字往后方的树填充

calculateMKAverage 直接使用中间数字之和 sum 求平均

3、代码​

var MKAverage = function (m, k) {
    this.m = m;
    this.k = k;

    this.nums = [];
    this.trees = [new AVLTree(), new AVLTree(), new AVLTree()];
    this.sum = 0;
};

MKAverage.prototype.addElement = function (num) {
    this.nums.push(num);
    const trees = this.trees;

    // remove
    if (this.nums.length > this.m) {
        const n = this.nums[this.nums.length - this.m - 1];
        let i = trees.findIndex(t => t.contains(n));

        if (i === 1) this.sum -= n;
        trees[i].remove(n);

        for (; i < trees.length - 1 && trees[i + 1].size > 0; i++) {
            const tmin = trees[i + 1].min();
            trees[i + 1].remove(tmin);
            trees[i].insert(tmin);
            if (i === 0) this.sum -= tmin;
            else if (i === 1) this.sum += tmin;
        }
    }

    // insert
    for (let i = 0; i < trees.length; i++) {
        const c = i !== 1 ? this.k : this.m - 2 * this.k;
        trees[i].insert(num);
        if (i === 1) this.sum += num;

        if (trees[i].size <= c) break;

        num = trees[i].max();
        trees[i].remove(num);
        if (i === 1) this.sum -= num;
    }
};

MKAverage.prototype.calculateMKAverage = function () {
    return this.nums.length < this.m ? -1 : (this.sum / (this.m - 2 * this.k)) >> 0;
};

// https://github.com/w8r/avl/
function print(root,printNode){if(printNode===void 0)printNode=function(n){return n.key};var out=[];row(root,'',true,function(v){return out.push(v)},printNode);return out.join('')}function row(root,prefix,isTail,out,printNode){if(root){out((""+prefix+(isTail?'└── ':'├── ')+(printNode(root))+"\n"));var indent=prefix+(isTail?'    ':'│   ');if(root.left){row(root.left,indent,false,out,printNode)}if(root.right){row(root.right,indent,true,out,printNode)}}}function isBalanced(root){if(root===null){return true}var lh=height(root.left);var rh=height(root.right);if(Math.abs(lh-rh)<=1&&isBalanced(root.left)&&isBalanced(root.right)){return true}return false}function height(node){return node?(1+Math.max(height(node.left),height(node.right))):0}function loadRecursive(parent,keys,values,start,end){var size=end-start;if(size>0){var middle=start+Math.floor(size/2);var key=keys[middle];var data=values[middle];var node={key:key,data:data,parent:parent};node.left=loadRecursive(node,keys,values,start,middle);node.right=loadRecursive(node,keys,values,middle+1,end);return node}return null}function markBalance(node){if(node===null){return 0}var lh=markBalance(node.left);var rh=markBalance(node.right);node.balanceFactor=lh-rh;return Math.max(lh,rh)+1}function sort(keys,values,left,right,compare){if(left>=right){return}var pivot=keys[(left+right)>>1];var i=left-1;var j=right+1;while(true){do{i++}while(compare(keys[i],pivot)<0);do{j--}while(compare(keys[j],pivot)>0);if(i>=j){break}var tmp=keys[i];keys[i]=keys[j];keys[j]=tmp;tmp=values[i];values[i]=values[j];values[j]=tmp}sort(keys,values,left,j,compare);sort(keys,values,j+1,right,compare)}function DEFAULT_COMPARE(a,b){return a>b?1:a<b?-1:0}function rotateLeft(node){var rightNode=node.right;node.right=rightNode.left;if(rightNode.left){rightNode.left.parent=node}rightNode.parent=node.parent;if(rightNode.parent){if(rightNode.parent.left===node){rightNode.parent.left=rightNode}else{rightNode.parent.right=rightNode}}node.parent=rightNode;rightNode.left=node;node.balanceFactor+=1;if(rightNode.balanceFactor<0){node.balanceFactor-=rightNode.balanceFactor}rightNode.balanceFactor+=1;if(node.balanceFactor>0){rightNode.balanceFactor+=node.balanceFactor}return rightNode}function rotateRight(node){var leftNode=node.left;node.left=leftNode.right;if(node.left){node.left.parent=node}leftNode.parent=node.parent;if(leftNode.parent){if(leftNode.parent.left===node){leftNode.parent.left=leftNode}else{leftNode.parent.right=leftNode}}node.parent=leftNode;leftNode.right=node;node.balanceFactor-=1;if(leftNode.balanceFactor>0){node.balanceFactor-=leftNode.balanceFactor}leftNode.balanceFactor-=1;if(node.balanceFactor<0){leftNode.balanceFactor+=node.balanceFactor}return leftNode}var AVLTree=function AVLTree(comparator,noDuplicates){if(noDuplicates===void 0)noDuplicates=false;this._comparator=comparator||DEFAULT_COMPARE;this._root=null;this._size=0;this._noDuplicates=!!noDuplicates};var prototypeAccessors={size:{configurable:true}};AVLTree.prototype.destroy=function destroy(){return this.clear()};AVLTree.prototype.clear=function clear(){this._root=null;this._size=0;return this};prototypeAccessors.size.get=function(){return this._size};AVLTree.prototype.contains=function contains(key){if(this._root){var node=this._root;var comparator=this._comparator;while(node){var cmp=comparator(key,node.key);if(cmp===0){return true}else if(cmp<0){node=node.left}else{node=node.right}}}return false};AVLTree.prototype.next=function next(node){var successor=node;if(successor){if(successor.right){successor=successor.right;while(successor.left){successor=successor.left}}else{successor=node.parent;while(successor&&successor.right===node){node=successor;successor=successor.parent}}}return successor};AVLTree.prototype.prev=function prev(node){var predecessor=node;if(predecessor){if(predecessor.left){predecessor=predecessor.left;while(predecessor.right){predecessor=predecessor.right}}else{predecessor=node.parent;while(predecessor&&predecessor.left===node){node=predecessor;predecessor=predecessor.parent}}}return predecessor};AVLTree.prototype.forEach=function forEach(callback){var current=this._root;var s=[],done=false,i=0;while(!done){if(current){s.push(current);current=current.left}else{if(s.length>0){current=s.pop();callback(current,i++);current=current.right}else{done=true}}}return this};AVLTree.prototype.range=function range(low,high,fn,ctx){var Q=[];var compare=this._comparator;var node=this._root,cmp;while(Q.length!==0||node){if(node){Q.push(node);node=node.left}else{node=Q.pop();cmp=compare(node.key,high);if(cmp>0){break}else if(compare(node.key,low)>=0){if(fn.call(ctx,node)){return this}}node=node.right}}return this};AVLTree.prototype.keys=function keys(){var current=this._root;var s=[],r=[],done=false;while(!done){if(current){s.push(current);current=current.left}else{if(s.length>0){current=s.pop();r.push(current.key);current=current.right}else{done=true}}}return r};AVLTree.prototype.values=function values(){var current=this._root;var s=[],r=[],done=false;while(!done){if(current){s.push(current);current=current.left}else{if(s.length>0){current=s.pop();r.push(current.data);current=current.right}else{done=true}}}return r};AVLTree.prototype.at=function at(index){var current=this._root;var s=[],done=false,i=0;while(!done){if(current){s.push(current);current=current.left}else{if(s.length>0){current=s.pop();if(i===index){return current}i++;current=current.right}else{done=true}}}return null};AVLTree.prototype.minNode=function minNode(){var node=this._root;if(!node){return null}while(node.left){node=node.left}return node};AVLTree.prototype.maxNode=function maxNode(){var node=this._root;if(!node){return null}while(node.right){node=node.right}return node};AVLTree.prototype.min=function min(){var node=this._root;if(!node){return null}while(node.left){node=node.left}return node.key};AVLTree.prototype.max=function max(){var node=this._root;if(!node){return null}while(node.right){node=node.right}return node.key};AVLTree.prototype.isEmpty=function isEmpty(){return!this._root};AVLTree.prototype.pop=function pop(){var node=this._root,returnValue=null;if(node){while(node.left){node=node.left}returnValue={key:node.key,data:node.data};this.remove(node.key)}return returnValue};AVLTree.prototype.popMax=function popMax(){var node=this._root,returnValue=null;if(node){while(node.right){node=node.right}returnValue={key:node.key,data:node.data};this.remove(node.key)}return returnValue};AVLTree.prototype.find=function find(key){var root=this._root;var subtree=root,cmp;var compare=this._comparator;while(subtree){cmp=compare(key,subtree.key);if(cmp===0){return subtree}else if(cmp<0){subtree=subtree.left}else{subtree=subtree.right}}return null};AVLTree.prototype.insert=function insert(key,data){if(!this._root){this._root={parent:null,left:null,right:null,balanceFactor:0,key:key,data:data};this._size++;return this._root}var compare=this._comparator;var node=this._root;var parent=null;var cmp=0;if(this._noDuplicates){while(node){cmp=compare(key,node.key);parent=node;if(cmp===0){return null}else if(cmp<0){node=node.left}else{node=node.right}}}else{while(node){cmp=compare(key,node.key);parent=node;if(cmp<=0){node=node.left}else{node=node.right}}}var newNode={left:null,right:null,balanceFactor:0,parent:parent,key:key,data:data};var newRoot;if(cmp<=0){parent.left=newNode}else{parent.right=newNode}while(parent){cmp=compare(parent.key,key);if(cmp<0){parent.balanceFactor-=1}else{parent.balanceFactor+=1}if(parent.balanceFactor===0){break}else if(parent.balanceFactor<-1){if(parent.right.balanceFactor===1){rotateRight(parent.right)}newRoot=rotateLeft(parent);if(parent===this._root){this._root=newRoot}break}else if(parent.balanceFactor>1){if(parent.left.balanceFactor===-1){rotateLeft(parent.left)}newRoot=rotateRight(parent);if(parent===this._root){this._root=newRoot}break}parent=parent.parent}this._size++;return newNode};AVLTree.prototype.remove=function remove(key){if(!this._root){return null}var node=this._root;var compare=this._comparator;var cmp=0;while(node){cmp=compare(key,node.key);if(cmp===0){break}else if(cmp<0){node=node.left}else{node=node.right}}if(!node){return null}var returnValue=node.key;var max,min;if(node.left){max=node.left;while(max.left||max.right){while(max.right){max=max.right}node.key=max.key;node.data=max.data;if(max.left){node=max;max=max.left}}node.key=max.key;node.data=max.data;node=max}if(node.right){min=node.right;while(min.left||min.right){while(min.left){min=min.left}node.key=min.key;node.data=min.data;if(min.right){node=min;min=min.right}}node.key=min.key;node.data=min.data;node=min}var parent=node.parent;var pp=node;var newRoot;while(parent){if(parent.left===pp){parent.balanceFactor-=1}else{parent.balanceFactor+=1}if(parent.balanceFactor<-1){if(parent.right.balanceFactor===1){rotateRight(parent.right)}newRoot=rotateLeft(parent);if(parent===this._root){this._root=newRoot}parent=newRoot}else if(parent.balanceFactor>1){if(parent.left.balanceFactor===-1){rotateLeft(parent.left)}newRoot=rotateRight(parent);if(parent===this._root){this._root=newRoot}parent=newRoot}if(parent.balanceFactor===-1||parent.balanceFactor===1){break}pp=parent;parent=parent.parent}if(node.parent){if(node.parent.left===node){node.parent.left=null}else{node.parent.right=null}}if(node===this._root){this._root=null}this._size--;return returnValue};AVLTree.prototype.load=function load(keys,values,presort){if(keys===void 0)keys=[];if(values===void 0)values=[];if(this._size!==0){throw new Error('bulk-load: tree is not empty');}var size=keys.length;if(presort){sort(keys,values,0,size-1,this._comparator)}this._root=loadRecursive(null,keys,values,0,size);markBalance(this._root);this._size=size;return this};AVLTree.prototype.isBalanced=function isBalanced$1(){return isBalanced(this._root)};AVLTree.prototype.toString=function toString(printNode){return print(this._root,printNode)};Object.defineProperties(AVLTree.prototype,prototypeAccessors);

4、复杂度​

  • 时间复杂度：addElement：O(logn)O(logn)，calculateMKAverage：O(1)O(1)
  • 空间复杂度：O(n)O(n)

5、执行结果​

image.png

· 阅读需 4 分钟

1、题干​

设计一个找到数据流中第 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 个元素

 

注意：本题与主站 703 题相同： https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

2、解法1-优先队列​

使用优先队列解题，初始化时把所有元素加入到最小优先队列pq中，添加元素时直接把元素加入pq，若pq元素个数小于k则直接返回-1，若pq元素个数超过k则逐一移除最后返回队头元素。


3、代码​

var KthLargest = function (k, nums) {
    this.k = k;
    this.pq = new MinPriorityQueue({ compare: (a, b) => a - b });
    for (const n of nums) this.pq.enqueue(n);
};

KthLargest.prototype.add = function (val) {
    this.pq.enqueue(val);
    if (this.pq.size() < this.k) return -1;
    while (this.pq.size() > this.k) this.pq.dequeue();
    return this.pq.front();
};

4、复杂度​

  • 时间复杂度：O(nlogn)O(nlogn)
  • 空间复杂度：O(n)O(n)

5、执行结果​

执行用时: 132 ms 内存消耗: 46.6 MB


6、解法2-计数排序​

对数据流使用计数排序，首次确定第 k 大元素 kIdx 需要遍历所有元素；此后添加数据需要再确定第 k 大元素时，如果添加的数据比 kIdx 小则直接返回 kIdx ；如果添加的数据比 kIdx 小则从下标 kIdx 开始在容器 list 找到更大且元素值不为0的下标返回即可。


这个题目中使用该算法坑略多，只作参考，不建议使用。


7、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

8、代码​

var KthLargest = function (k, nums) {
    this.k = k;
    this.size = nums.length;
    this.kIdx = -1;
    this.list = new Array(2e4 + 1).fill(0);
    for (const n of nums) this.list[n + 1e4]++;
};

KthLargest.prototype.add = function (val) {
    (val += 1e4), this.list[val]++, this.size++;
    if (this.size < this.k) return -1;

    if (this.kIdx < 0) {
        for (let i = this.list.length - 1, k = this.k; i >= 0; i--) {
            if (k < this.list[i]) this.list[i] = k;
            if ((k -= this.list[i]) <= 0) {
                this.kIdx = i;
                break;
            }
        }
        return this.kIdx - 1e4;
    }

    if (this.size > this.k && val >= this.kIdx) {
        this.list[this.kIdx]--;
        for (let i = this.kIdx; i < this.list.length; i++) {
            if (this.list[i]) {
                this.kIdx = i;
                break;
            }
        }
    }

    return this.kIdx - 1e4;
};

9、执行结果​

1.png

· 阅读需 4 分钟

1、题干​

设计一个找到数据流中第 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 个元素

 

注意：本题与主站 703 题相同： https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

2、解法1-优先队列​

使用优先队列解题，初始化时把所有元素加入到最小优先队列pq中，添加元素时直接把元素加入pq，若pq元素个数小于k则直接返回-1，若pq元素个数超过k则逐一移除最后返回队头元素。


3、代码​

var KthLargest = function (k, nums) {
    this.k = k;
    this.pq = new MinPriorityQueue({ compare: (a, b) => a - b });
    for (const n of nums) this.pq.enqueue(n);
};

KthLargest.prototype.add = function (val) {
    this.pq.enqueue(val);
    if (this.pq.size() < this.k) return -1;
    while (this.pq.size() > this.k) this.pq.dequeue();
    return this.pq.front();
};

4、复杂度​

  • 时间复杂度：O(nlogn)O(nlogn)
  • 空间复杂度：O(n)O(n)

5、执行结果​

执行用时: 132 ms 内存消耗: 46.6 MB


6、解法2-计数排序​

对数据流使用计数排序，首次确定第 k 大元素 kIdx 需要遍历所有元素；此后添加数据需要再确定第 k 大元素时，如果添加的数据比 kIdx 小则直接返回 kIdx ；如果添加的数据比 kIdx 小则从下标 kIdx 开始在容器 list 找到更大且元素值不为0的下标返回即可。


这个题目中使用该算法坑略多，只作参考，不建议使用。


7、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

8、代码​

var KthLargest = function (k, nums) {
    this.k = k;
    this.size = nums.length;
    this.kIdx = -1;
    this.list = new Array(2e4 + 1).fill(0);
    for (const n of nums) this.list[n + 1e4]++;
};

KthLargest.prototype.add = function (val) {
    (val += 1e4), this.list[val]++, this.size++;
    if (this.size < this.k) return -1;

    if (this.kIdx < 0) {
        for (let i = this.list.length - 1, k = this.k; i >= 0; i--) {
            if (k < this.list[i]) this.list[i] = k;
            if ((k -= this.list[i]) <= 0) {
                this.kIdx = i;
                break;
            }
        }
        return this.kIdx - 1e4;
    }

    if (this.size > this.k && val >= this.kIdx) {
        this.list[this.kIdx]--;
        for (let i = this.kIdx; i < this.list.length; i++) {
            if (this.list[i]) {
                this.kIdx = i;
                break;
            }
        }
    }

    return this.kIdx - 1e4;
};

9、执行结果​

1.png