# 493 Reverse Pairs

## 493. [Reverse Pairs](https://leetcode.com/problems/reverse-pairs/description/)

## 1. Question

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:**

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

## 2. Implementation

**(1) Merge Sort**

```java
class Solution {
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        int[] res = new int[1];
        mergeSort(nums, 0, n - 1, res);
        return res[0];
    }

    public void mergeSort(int[] nums, int start, int end, int[] res) {
        if (start >= end) {
            return;
        }

        int mid = start + (end - start) / 2;
        mergeSort(nums, start, mid, res);
        mergeSort(nums, mid + 1, end, res);

        int count = 0;
        int left = start, right = mid + 1;

        while (left <= mid) {
            if (right <= end && (nums[left] > 2 * (long)nums[right])) {
                ++count;
                ++right;
            }
            else {
                res[0] += count;
                ++left;
            }
        }
        merge(nums, start, mid, end);
    }

    public void merge(int[] nums, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];

        int i = start;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= end) {
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            }
            else {
                temp[k++] = nums[j++];
            }
        }

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

        while (j <= end) {
            temp[k++] = nums[j++];
        }

        for (int m = start; m <= end; m++) {
            nums[m] = temp[m - start];
        }
    }
}
```

## 3. Time & Space Complexity

**Merge Sort:**&#x65F6;间复杂度O(nlogn), 空间复杂度O(n)