树状数组 – CheungQ

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

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

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

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

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

输入： ["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

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

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

示例 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】数组中的逆序对