[leetCode]493. 翻转对

题目

链接：https://leetcode-cn.com/problems/reverse-pairs

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

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

示例 1:

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

示例 2:

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

注意:

给定数组的长度不会超过50000。
输入数组中的所有数字都在32位整数的表示范围内。

归并排序

• 使用归并排序先将数组分解成小数组
• 再进行归并操作之前先计算重要翻转对的个数
• 再将左右子数组归并形成一个排序数组，重复上面的过程

class Solution {
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        return mergeSort(nums, 0, nums.length - 1);
    }

    private int mergeSort(int[] nums, int lo, int hi) {
        if (lo >= hi) return 0;

        int mid = lo + (hi - lo) / 2;
        int ans = 0;
        ans += mergeSort(nums, lo, mid);
        ans += mergeSort(nums, mid + 1, hi);
        ans += merge(nums, lo, mid, hi);
        return ans;
    }

    private int merge(int[] nums, int lo, int mid,int hi) {
        int i = lo, j = mid + 1;
        int count = 0;
        while (i <= mid && j <= hi) {
            if ((long)nums[i] > 2 * (long)nums[j]) { 
                // 1,3,4
                // 1,2,3
                count += mid - i + 1;
                j++;
            } else {
                i++;
            }
        }
        i = lo;
        j = mid + 1;
        int[] aux = new int[hi - lo + 1];
        int index = 0;
        while (i <= mid && j <= hi) {
            if (nums[i] > nums[j]) {
                aux[index++] = nums[j++];
            } else {
                aux[index++] = nums[i++];
            }
        }
        while (i <= mid) {
            aux[index++] = nums[i++];
        }
        while (j <= hi) {
            aux[index++] = nums[j++];
        }
        for (int k = 0; k < aux.length; k++) {
            nums[k + lo] = aux[k];
        }
        return count;
    }

}