面试题 10.10. 数字流的秩
题目
假设你正在读取一串整数。每隔一段时间,你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。 请实现数据结构和算法来支持这些操作,也就是说:
实现 track(int x)方法,每读入一个数字都会调用该方法;
实现 getRankOfNumber(int x) 方法,返回小于或等于 x 的值的个数。
注意:本题相对原题稍作改动
示例:
输入: [“StreamRank”, “getRankOfNumber”, “track”, “getRankOfNumber”] [[], [1], [0], [0]]
输出: [null,0,null,1]
提示:
- x <= 50000
- track和getRankOfNumber 方法的调用次数均不超过 2000 次
题解
class StreamRank {
int[] data;
int max;
public StreamRank() {
// 最大数字为50000
this.data = new int[50001];
// 最大值
this.max = 0;
}
public void track(int x) {
// 后续数字追加1
for (int i = x; i <= this.max; i++) {
this.data[i]++;
}
// 若为新的最大值
if (this.max < x) {
// 当前最大值之后赋值为当前最大值的佚
Arrays.fill(this.data, this.max + 1, x + 1, this.data[this.max]);
// 新的最大值佚加1
this.data[x]++;
// 更新最大值
this.max = x;
}
}
public int getRankOfNumber(int x) {
// x小于最大值 返回x的佚 否则返回最大值的佚
return this.data[Integer.min(x, this.max)];
}
}