面试题 10.10. 数字流的秩

题目

题目来源：力扣（LeetCode）

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：

实现 track(int x) 方法，每读入一个数字都会调用该方法；

实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。

注意：本题相对原题稍作改动

示例:

输入:
[“StreamRank”, “getRankOfNumber”, “track”, “getRankOfNumber”]
[[], [1], [0], [0]]
输出:
[null,0,null,1]

思路分析

track将x..n区间的所有计数+1

getRankOfNumber累计0..x区间的所有计数

每次输⼊⼀个新x值，假设有arr[i]

var StreamRank = function () {
  this.arr = new Array(50001).fill(0);
};
/**
 * @param {number} x
 * @return {void}
 */
StreamRank.prototype.track = function (x) {
  this.arr[x] += 1;
};
/**
 * @param {number} x
 * @return {number}
 */
StreamRank.prototype.getRankOfNumber = function (x) {
  let total = 0;
  for (let i = 0; i <= x; i++) {
    total += this.arr[i];
  }
  return total;
};
/**
 * Your StreamRank object will be instantiated and called as such:
 * var obj = new StreamRank()
 * obj.track(x)
 * var param_2 = obj.getRankOfNumber(x)
 */