LeetCode刷题【面试题 10.10】数字流的秩

输入:
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
输出:
[null,0,null,1]

树状数组结构直接套模板使用

在该题中，树状数组对应下标表意为当前下标数字的出现次数

1. track(int x) 方法，每读入一个数字都会调用该方法, 等价于在给树状数组对应下标数值加1，即当前下标出现次数加1
2. getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数，等价于求下标0到当前下标的前缀和，即从0到当前下标的所有数字出现次数之和

代码

class StreamRank {

    private FenwickTree fenwickTree;


    public StreamRank() {
        fenwickTree = new FenwickTree(50001);
    }

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

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


    class FenwickTree{
        int[] arr;
        public FenwickTree(int num){
            arr = new int[num+1];
        }

        int lowBit(int x){
            return x & ( -x );
        }

        public void add(int idx, int num){
            while (idx < arr.length){
                arr[idx] += num;
                idx += lowBit(idx);
            }
        }

        public int query(int idx){
            int sum = 0;
            while (idx > 0){
                sum += arr[idx];
                idx -= lowBit(idx);
            }
            return sum;
        }
    }
}