面试题 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)];
    }
}