标签：树状数组

LeetCode刷题【1409】查询带键的排列

2022 年 6 月 29 日 / CheungQ / 0 Comments

给你一个待查数组 queries ，数组中的元素为 1 到 m 之间的正整数。请你根据以下规则处理所有待查项 queries[i]（从 i=0 到 i=queries.length-1）：

一开始，排列 P=[1,2,3,...,m]。
对于当前的 i ，请你找出待查项 queries[i] 在排列 P 中的位置（下标从 0 开始），然后将其从原位置移动到排列 P 的起始位置（即下标为 0 处）。注意， queries[i] 在 P 中的位置就是 queries[i] 的查询结果。

请你以数组形式返回待查数组 queries 的查询结果。

示例 1：

输入：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] 。

示例 2：

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

示例 3：

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

提示：

1 <= m <= 10^3
1 <= queries.length <= m
1 <= queries[i] <= m

Related Topics

树状数组
数组
模拟

👍 39

👎 0

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

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

    }
}

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

2022 年 6 月 29 日 / CheungQ / 0 Comments

假设你正在读取一串整数。每隔一段时间，你希望能找出数字 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 次

Related Topics

设计
树状数组
二分查找
数据流

👍 32

👎 0

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

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

track(int x) 方法，每读入一个数字都会调用该方法, 等价于在给树状数组对应下标数值加1，即当前下标出现次数加1
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;
        }
    }
}

LeetCode刷题【307】区域和检索 – 数组可修改

2022 年 6 月 29 日 / CheungQ / 0 Comments

给你一个数组 nums ，请你完成两类查询。

其中一类查询要求更新数组 nums 下标对应的值
另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（包含）的nums元素的和，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值更新为 val
int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（包含）的nums元素的和（即，nums[left] + nums[left + 1], ..., nums[right]）

示例 1：

输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

提示：

1 <= nums.length <= 3 * 10⁴
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
调用 update 和 sumRange 方法次数不大于 3 * 10⁴

Related Topics

设计
树状数组
线段树
数组

👍 521

👎 0

树状数组套模板

class NumArray {

    private FenwickTree fenwickTree;

    public NumArray(int[] nums) {
        fenwickTree = new FenwickTree(nums.length);
        for (int i = 0; i < nums.length; i++) {
            fenwickTree.add(i+1,nums[i]);
        }
    }

    public void update(int index, int val) {
        fenwickTree.add(index+1,val - fenwickTree.queryIndex(index+1));
    }

    public int sumRange(int left, int right) {
        return fenwickTree.rangeSum(left,right+1);
    }


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

        public 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 querySum(int idx){
            int res = 0;
            while (idx > 0){
                res += arr[idx];
                idx -= lowBit(idx);
            }
            return res;
        }

        public int queryIndex(int idx){
            return querySum(idx) - querySum(idx-1);
        }

        public int rangeSum(int left, int right){
            if (left > right){
                int tmp = right;
                right = left;
                left = tmp;
            }
            return querySum(right) - querySum(left);
        }
    }
}

LeetCode刷题【剑指 Offer 51】数组中的逆序对

2022 年 5 月 27 日 / CheungQ / 0 Comments

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

限制：

0 <= 数组长度 <= 50000

Related Topics

树状数组

线段树

数组

二分查找

分治

有序集合

归并排序

👍 748

👎 0

归并，基本思路李姐

归并过程可以把代码的注释打开看下，以实际数据来解释说明下

    归并数组： [7, 6, 5, 4, 3]   [32, 11, 8, 2, 1]
    idxL:0
    idxR:3
    2
    idxL:1
    idxR:3
    2
    idxL:2
    idxR:3
    2
    idxL:3
    idxR:3
    2
    idxL:4
    idxR:3
    2
    归并结果： [32, 11, 8, 7, 6, 5, 4, 3, 2, 1]
    -----

以上数组A[7, 6, 5, 4, 3]、B[32, 11, 8, 2, 1]

合并的时候，A的第0个7小于B的第0个32，结果第一位插入32，第二位11同样，第三位8同样
A下标0的数字7大于B下标3的数字2，此时7和后面的[2, 1]形成逆序对，逆序对个数加2
6同样和后面的[2, 1]形成逆序对，逆序对个数加2
[5, 4, 3]也一样，逆序对分别加2
而在这之前的A数组内部的逆序对，在最开始之前的时候做归并排序

    归并数组： [7]   [5]
    idxL:0
    idxR:0
    1
    归并结果： [7, 5]
    -----

以及归并数组： [7, 5] [6]和归并数组： [4] [3]，再将这两个合并归并数组： [7, 6, 5] [4, 3]，得到结果[7, 6, 5, 4, 3]，在这个过程中已经计算过了

class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        sort(nums);
        return count;
    }

    public int[] sort(int[] nums){
        if (nums.length<2){
            return nums;
        }
        int[] right = new int[nums.length/2];
        int[] left = new int[nums.length - right.length];
        System.arraycopy(nums,0,left,0,left.length);
        System.arraycopy(nums,left.length,right,0,right.length);
        left = sort(left);
        right = sort(right);
        return mergeArray(left,right);
    }

    public int[] mergeArray(int[] left, int[] right) {
        if (right.length==0){
            return left;
        }
//        System.out.println("归并数组： "+Arrays.toString(left) +"   "+ Arrays.toString(right));
        int[] arr = new int[left.length + right.length];
        int idx = -1;
        int idxL = 0;
        int idxR = 0;
        while (++idx < arr.length){
            if (idxL<left.length && (idxR>= right.length || left[idxL] > right[idxR])){
                arr[idx] = left[idxL];
                idxL++;
                count += right.length-idxR;
//                System.out.println(right.length-idxR);
            }else{
                arr[idx] = right[idxR];
                idxR++;
            }
        }
//        System.out.println("归并结果： "+Arrays.toString(arr));
//        System.out.println("-----");
        return arr;
    }
}

近期文章

分类

文章归档

标签：树状数组

LeetCode刷题【1409】查询带键的排列

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

代码

LeetCode刷题【307】区域和检索 – 数组可修改

LeetCode刷题【剑指 Offer 51】数组中的逆序对