493 Reverse Pairs

493. Reverse Pairs

1. Question

Given an arraynums, we call(i, j)an important reverse pair ifi < jandnums[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 exceed50,000.

2. All the numbers in the input array are in the range of 32-bit integer.

2. Implementation

(1) Merge Sort

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:时间复杂度O(nlogn), 空间复杂度O(n)