题目:
假设你正在读取一串整数。每隔一段时间,你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作,也就是说:
实现 track(int x) 方法,每读入一个数字都会调用该方法;
实现 getRankOfNumber(int x) 方法,返回小于或等于 x 的值的个数。
注意:本题相对原题稍作改动
示例:
输入:
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
输出:
[null,0,null,1]
代码实现:
class StreamRank {标签:StreamRank,yyds,int,getRankOfNumber,list,public,track,金典,LeetCode From: https://blog.51cto.com/u_13321676/6065444
public StreamRank() {
list = new ArrayList<>();
}
List<Integer> list;
public void track(int x) {
int i = 0;
int j = list.size()-1;
while(i <= j){
int m = i + (j-i)/2;
if(list.get(m) < x){i = m+1;}
else{j = m-1;}
}// 寻找第一个比它大的数
list.add(i, x);// 在其下标处插入x
}
public int getRankOfNumber(int x) {
int i = 0;
int j = list.size()-1;
while(i <= j){
int m = i + (j-i)/2;
if(list.get(m) > x){j = m-1;}
else{i = m+1;}
}// 寻找最后一个不大于它的数
return j+1;// 下标加1才是元素数目(秩)
}
}