【英雄哥七月集训】第 24天： 线性树

---

一、剑指 Offer 51. 数组中的逆序对

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5

leetcode剑指 offer51 java

思路

离散 nums

(query)=右边的几个数比他小

将每一个位置的 u 相加,最后得到结果

class Solution {
    
    int n = 0, res = 0 , u = 0;
    
    public int reversePairs(int[] nums) {
    
        n = nums.length;
        //离散化
        descretize(nums);
        //初始化线段树
        Bit bit = new Bit(n);
        //遍历每一个节点,取当前节点的 query
        for(int i = n-1; i >=0 ; i--){
    
            //System.out.printf("%d %d\n",nums[i],bit.query(nums[i]-1));
            u = bit.query(nums[i]-1);
            res += u; 
            bit.update(nums[i]);
        }
        return res;
    }
    public void descretize(int[] nums){
    
        int[] temp = new int[n];
        System.arraycopy(nums,0,temp,0,n);
        Arrays.sort(temp);
        for(int i = 0; i <n ; i++){
    
            nums[i] = Arrays.binarySearch(temp,nums[i])+1;
        }
    }

    public class Bit{
    
        int n;
        int[] tree;
        public Bit(int x){
    
            this.n = x;
            this.tree = new int[x+1];
        }

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

        public void update(int x){
    
            while(x<=n){
    
                tree[x]++;
                x+=lowBit(x);
            }
        }
        public int query(int x){
    
            int ret = 0;
            while(x!=0){
    
                ret +=tree[x];
                x-=lowBit(x);
            }
            return ret;
        }
    }
}

---

总结