#yyds干货盘点# LeetCode程序员面试金典：数字流的秩

题目：

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

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

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

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

示例:

输入:

["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]

[[], [1], [0], [0]]

输出:

[null,0,null,1]

代码实现：

class StreamRank {

    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才是元素数目（秩）
    }
}