打卡系列-剑指 Offer 51. 数组中的逆序对(困难)

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

解析：

public static int reversePairs(int[] nums) {
        int[] temps = new int[nums.length];
        int count = reversePairs(nums , 0 , nums.length - 1 , temps);
        return count;
    }
    //分治计算
    public static int reversePairs(int[] nums , int start , int end , int[] temps){
        if(start >= end){
            return 0;
        }
        int mid = start + (end - start)/2;
        //左半边逆序对
        int left = reversePairs(nums , start , mid , temps);
        //右半边逆序对
        int right = reversePairs(nums , mid+1 , end , temps);
        //左边排序好与右边排序好的数，计算逆序对
        int count = 0;
        int r = mid + 1;
        int l = start;
        int index = start;
        while(l <= mid && r <= end){
            if(nums[l] > nums[r]){
                temps[index] = nums[r];
                count += mid - l + 1;
                r++;
            }else {
                temps[index] = nums[l];
                l++;
            }
            index++;
        }
        //左边还剩的数
        while (l <= mid){
            temps[index++] = nums[l++];
        }
        //右边还剩的数
        while (r <= end){
            temps[index++] = nums[r++];
        }
        for(;start <= end ; start++){
            nums[start] = temps[start];
        }
        return left + right + count;
    }

leetcode

分治思想