面试题51. 数组中的逆序对(困难)

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof

思路：

归并排序，需要了解归并排序解题模板

分治思想：

  1. 分两块，左右
  2. 分别计算，左边，右边
  3. 再计算横跨左右的

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int reversePairs(int[] nums) {      
        // int[] assist = new int[nums.length];
        return mergeSort(nums,0,nums.length-1);
    }
    public int mergeSort(int[] nums,int left,int right){
        if(left>=right)
            return 0;
        int mid = (right+left)>>1;
        //返回三段的总和，左，右，横跨左右
        return mergeSort(nums,left,mid)+mergeSort(nums,mid+1,right)+merge(nums,left,mid,right);
    }
    public int merge(int[] nums,int left,int mid,int right){
        int count =0;//计数
        int l = left;
        int r = mid +1;
        int index = 0;
        int[] assist = new int[right-left+1];
        while(l<=mid && r<=right){//左右不超
            if(nums[l]>nums[r])//如果r比l数小，那么r小于l位置后的所有数
                count += mid-l+1;//去掉这个if就是归并的模板
            assist[index++] = nums[l]<=nums[r]?nums[l++]:nums[r++];//放到排序数组中
        }
        //排完还剩的话
        while(l<=mid)
            assist[index++] = nums[l++];
        while(r<=right)
            assist[index++] = nums[r++];
        //可以用while
        //int current=0;
        //while(left<=right)
            //array[left++]=temp[current++];
        for (int i = 0,j=left; i < assist.length; i++,j++) {//在原来数组的基础上，继续添加进已排好的数列
            nums[j] = assist[i];
        }
        return count;
    }
}