【Leetcode】493.翻转对

493. 翻转对

题目

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:
输入: [1,3,2,3,1]
输出: 2

示例 2:
输入: [2,4,3,5,1]
输出: 3

方法（归并排序）

在一个数组中寻找元素对这样的情况都可以考虑归并排序的思路。

如果我们已经将数组的左右两部分nums[L……mid]、nums[mid+1……R]排好序。则对于右半部分的位置j，如果在左边有一个位置i满足nums[i] > 2*nums[j],那么从i到mid中的所有位置都可以和j组成翻转对（因为左半部分有序，位置i右边的元素肯定大于位置i处的元素）。

当找完了j位置的所有翻转对之后，接下来找j+1位置的翻转对。由于nums[j+1]大于nums[j]，因此i不用回退，一直向右移动判断即可。知道找出右半部分所有位置对应的翻转对数量。

总结一下，所有的翻转对由以下三部分构成：

  1. i和j都在nums的左半部分
  2. i和j都在nums的右半部分
  3. i在nums的左半部分，j在nums的右半部分。

上面我们讨论的是第三部分，第一部分和第二部分的翻转对递归求得即可。

也就是说我们在归并排序的同时，在merge操作的过程中顺带统计出了翻转对的数目。

代码

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
39
40
41
42
43
44
45
public int reversePairs(int[] nums) {
    if(nums == null || nums.length == 0)
        return 0;
    return mergeSort(nums, 0, nums.length - 1);
}

public int mergeSort(int[] nums, int left, int right){
    if(right == left)
        return 0;
    int mid = left + (right - left) / 2;
    //数组左半段内部产生的翻转对
    int count1 = mergeSort(nums, left, mid);
    //数组右半段内部产生的翻转对
    int count2 = mergeSort(nums, mid + 1, right);
    //翻转对的两端i和j分别在左半段和右半段时，产生的翻转对。
    int count3 = merge(nums, left, mid, right);
    return count1 + count2 + count3;
}

public int merge(int[] nums, int left, int mid, int right){
    int res = 0;
    int curL = left;
    for(int i = mid + 1; i <= right; i++){
        while(curL <= mid && (long)nums[curL] <= (long)2 * nums[i])
            curL++;
        res += mid - curL + 1;
    }
    int[] help = new int[right - left + 1];
    int index = 0;
    int L = left;
    int R = mid + 1;
    while(L <= mid && R <= right){
        help[index++] = nums[L] < nums[R] ? nums[L++] : nums[R++];
    }
    while(L <= mid){
        help[index++] = nums[L++];
    }
    while(R <= right){
        help[index++] = nums[R++];
    }
    for(int i = 0; i < help.length; i++){
        nums[i + left] = help[i];
    }
    return res;
}