数字流的秩

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 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 次
通过次数2,493提交次数4,017

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rank-from-stream-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class FenwickTree {
    int n;
    int[] C;

    //初始化
    public FenwickTree(int n) {
        this.n = n;
        this.C = new int[n];
    }

    // 单点更新：将 i 位置与其直接关联的 C 都更新一遍
    public void update(int i) {
        while (i < n) {
            C[i]++;
            i += lowbit(i);
        }
    }

    //传进来的值-1过，查询之前有多少个数
    //区间查询：查询小于等于 i 的元素个数
    public int query(int i) {
        int sum = 0;
        while (i >= 1) {
            sum += C[i];
            i -= lowbit(i);
        }
        return sum;
    }

    //算lowbit
    public int lowbit(int x) {
        return x & (-x);
    }
}

class StreamRank {
    FenwickTree fenwickTree;

    public StreamRank() {
        fenwickTree = new FenwickTree(50_005);
    }

    public void track(int x) {
        fenwickTree.update(x + 1);
    }

    public int getRankOfNumber(int x) {
      return fenwickTree.query(x + 1);
    }
}

作者：a-fei-8
链接：https://leetcode-cn.com/problems/rank-from-stream-lcci/solution/tao-yuan-san-xiong-zhi-zhi-shu-zi-liu-de-zhi-by-a-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

树状数组

树状数组学习笔记树状数组能解决的问题

赏

谢谢你请我吃糖果

微信