LeetCode 493. Reverse Pairs

Problem

剑指 Offer 51. 数组中的逆序对

1. 题目简述

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

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

限制：
0 <= 数组长度 <= 50000

2. 算法思路

这道题有两种做法，一种是分治法，或者说归并排序；另一种是树状数组。这里只写第一种做法，第二种工作法待更新。

分治法（归并排序）

对于一个数组，我们先将其分为两段，也就是两个数组，l和r，然后分别进行排序。排好序后，我们进行遍历，两个指针和j，一开始指向l[0]和r[0]，然后r指针不断向后移动，直到r[j] >= r[i]，此时，从mid+1到j之间的所有数字和l[0]构成逆序对！然后i也向后移，直到mid。这样一层层分下去，和归并算法的思路一致。

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

    public int mergeSort(int[] nums, int l, int r) {
        if (l >= r) {
            return 0;
        }

        int mid = l + r >> 1, res = 0;
        res += mergeSort(nums, l, mid) + mergeSort(nums, mid+1, r);

        // 此时，左右两侧数组已经有序
        for (int i = l, j = mid + 1; i <= mid; i++) {
            while (j <= r && nums[i] > nums[j]) {
                j++;
            }
            res += j - mid - 1;
        }

        // 开始归并排序
        int[] temp = new int[r - l + 1];
        int k = 0, i = l, j  = mid + 1;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= r) {
            temp[k++] = nums[j++];
        }

        for (int m = 0, n = l; m < temp.length; m++, n++) {
            nums[n] = temp[m];
        }

        return res;
    }
}