月度归档： 2022年6月

输入：queries = [3,1,2,1], m = 5
输出：[2,1,2,1] 
解释：待查数组 queries 处理如下：
对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 2，接着我们把 3 移动到 P 的起始位置，得到 P=[3,1,2,4,5] 。
对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 1，接着我们把 1 移动到 P 的起始位置，得到 P=[1,3,2,4,5] 。 
对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 2，接着我们把 2 移动到 P 的起始位置，得到 P=[2,1,3,4,5] 。
对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 1，接着我们把 1 移动到 P 的起始位置，得到 P=[1,2,3,4,5] 。 
因此，返回的结果数组为 [2,1,2,1] 。  

输入：queries = [4,1,2,2], m = 4
输出：[3,1,2,0]

输入：queries = [7,5,5,8,3], m = 8
输出：[6,5,0,7,5]

树状数组实现
思路同官方题解

1. 树状数组的长度为queries.length + m，把原先的m序列在树状数组中后面部分构件起来
2. 这样移动某个数字到前面的时候，就等于把树状数组后面的这个数字，往前面部分移动，需要在树状数组中对后面的key进行减1，并在前面移动到的新位置加1
3. 这样需要维护一个数组记录每个数字当前所在的索引下标，移动到前面的时候更新索引下标为前面的值
4. 每次查询当前位置前面的前缀和即为前面有多少个数字，并需要减1，因为包含了当前数字

class Solution {
    public int[] processQueries(int[] queries, int m) {
        int l = queries.length + m;
        FenwickTree fenwickTree = new FenwickTree(l);
        int[] numPos = new int[m+1];
        for (int i = queries.length + 1; i <= l; i++) {
            fenwickTree.add(i,1);
            numPos[i - queries.length] = i;
        }

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int num = queries[i];
            res[i] = fenwickTree.query(numPos[num]) - 1;
            fenwickTree.add(numPos[num],-1);
            numPos[num] = queries.length - i;
            fenwickTree.add(numPos[num],1);
        }
        return res;
    }

    class FenwickTree{
        int[] arr;

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

        public int lowBit(int i){
            return i & (-i);
        }

        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;
        }

    }
}