493. Reverse Pairs

LeetCode Divide and Conquer Binary Indexed Tree Segment Tree Binary Search Tree

Given an array nums, we call (i, j) an important reverse pair if $i < j$ and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2

Example2:

Input: [2,4,3,5,1]
Output: 3

Note:

• The length of the given array will not exceed 50,000.
• All the numbers in the input array are in the range of 32-bit integer.

分析

翻转对。使用分治的思想，借鉴归并排序，将数组分解后合并，最后按从小到大排列。在归并的过程中计算翻转对的数量。主要有两个难点：

• 合并的部分，这一过程完全和归并排序相同。
• 计算翻转对的数量的过程，下面将详细讨论。

寻找左数组和右数组构成的翻转对(左数组内部和右数组内部的翻转对已经递归求解): 将两个指针$i,j$分别指向左右数组的开始位置(分别为start, end+1)，并每次比较两个指针指向的数字。

• 如果第一个指针$i$指向的数字nums$[i]$大于第二个指针nums$[j]$指向的数字的2倍(nums$[i]$ > 2*nums$[j]$)，即满足翻转对条件，那么就寻找到了一个翻转对。
• 接下来一直尝试着移动右指针$j$，右指针指向的数字增加，直到某一个位置会不满足翻转对条件。
• 此时右数组的开始位置($mid+1$)直到右指针的前一个位置$(j-1)$间的数字和左指针指向的数字都构成翻转对。

private  int[] aux;
public int reversePairs(int[] nums) {
    aux = new int[nums.length];
    return mergesort_and_count(nums, 0, nums.length - 1);
}

private int mergesort_and_count(int[] nums, int start, int end) {
    if (start >= end) return 0;    // 只有1/0个数字，当然没有翻转对
    int mid = start + (end - start) / 2;              // 中间点
    int count = mergesort_and_count(nums, start, mid)  // 左边
            + mergesort_and_count(nums, mid + 1, end); // 右边
    // 计算翻转对数量，i为左边指针，j为右边指针
    for (int i = start, j = mid + 1; i <= mid; i++) {
        // 当满足重要翻转对的条件时，移动右边指针，直到不满足条件
        while (j <= end && nums[i] > nums[j] * 2L) j++;
        // mid～j之间的数字与i都满足重要反转对的条件，把这部分计算进去
        count += j - (mid + 1);
    }
    merge(nums, start, mid, end);
    return count;
}

// 合并：左半部分：start ~ mid, 右半部分:mid+1 ~ end, included
private void merge(int[] nums, int start, int mid, int end) {
    System.arraycopy(nums, start, aux, start, end - start + 1);
    int i = start, j = mid + 1;
    // 合并：将较小的元素放在前边
    for (int k = start; k <= end; k++) {
        if (i > mid)                nums[k] = aux[j++];
        else if (j > end)           nums[k] = aux[i++];
        else if (aux[i] > aux[j])   nums[k] = aux[j++];
        else                        nums[k] = aux[i++];
    }
}