数组中的逆序对

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

示例 1:

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

限制：

0 <= 数组长度 <= 50000

题解

利用归并排序的局部有序，就可以批量知道左右的大小关系。

如图，1小先走，则右边的全部比1大。所以只需要加上右边的就可以了。

  public int reversePairs(int[] nums) {
    if (nums == null || nums.length < 2) {
        return 0;
    }
    int k = mergeSort(nums, 0, nums.length - 1);
    System.out.println(Arrays.toString(nums));
    return k;
}


//先分成，2段，计算2段之前的逆序对
private int mergeSort(int[] nums, int left, int right) {

    if (left == right) return 0;
    int mid = (left + right) / 2;
    int leftCount = mergeSort(nums, left, mid);//计算左边部分
    int rightCount = mergeSort(nums, mid+1, right);//计算右边部分

    return leftCount+rightCount+merger(nums, left, mid, right);
}

//真实merge,计算以mid分界的逆序对
private int merger(int[] nums,int left ,int mid,int right){

    //最终归并的数组
    int[] temp = new int[right - left + 1];
    int count = 0;
    int p1 = left;
    int p2 = mid + 1;
    int i = 0;
    //以mid分界
    while (p1 <= mid && p2 <= right) {
        if (nums[p1] <= nums[p2]) {
            //p1比较小，p1入队
            temp[i++] = nums[p1++];
        }else {
            //p2入队
            temp[i++] = nums[p2++];
            //加上左边的数，就逆序对数
            count += mid - p1 +1 ;
        }

    }

    //接下来处理某一个有剩余的情况,谁剩下，谁全部移交到temp

    while (p1 <= mid) {
        temp[i++] = nums[p1++];
    }

    while (p2 <= right) {
        temp[i++] = nums[p2++];
    }

    //排序好的，copy到源数组

    for (int j = 0; j < temp.length; j++) {
        nums[left + j] = temp[j];
    }
    return count;
}