Formatted question description: https://leetcode.ca/all/493.html

493. Reverse Pairs

Level

Hard

Description

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.

Example 1:

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

Output: 2

Example 2:

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.

Solution

Use the idea of merge sort. In merge sort, the original array is split into two parts, each of which is sorted, and then merged. Suppose the two parts have already been sorted. Before merging the two parts, if there exists an index i in the left part and an index j in the right part such that nums[i] > 2 * nums[j], then all indices from i to the end of the left part have numbers greater than 2 * nums[j], so increase the count accordingly.

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

    public int mergeSortAndCount(int[] nums, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            int midIndex = (endIndex - startIndex) / 2 + startIndex;
            int count = mergeSortAndCount(nums, startIndex, midIndex) + mergeSortAndCount(nums, midIndex + 1, endIndex);
            int index1 = startIndex, index2 = midIndex + 1;
            while (index1 <= midIndex && index2 <= endIndex) {
                if ((long) nums[index1] > 2 * (long) nums[index2]) {
                    count += midIndex - index1 + 1;
                    index2++;
                } else
                    index1++;
            }
            merge(nums, startIndex, midIndex, endIndex);
            return count;
        } else
            return 0;
    }

    public void merge(int[] nums, int startIndex, int midIndex, int endIndex) {
        int length = endIndex - startIndex + 1;
        int[] newArray = new int[length];
        int index1 = startIndex, index2 = midIndex + 1;
        int index = 0;
        while (index1 <= midIndex && index2 <= endIndex) {
            if (nums[index1] <= nums[index2])
                newArray[index++] = nums[index1++];
            else
                newArray[index++] = nums[index2++];
        }
        while (index1 <= midIndex)
            newArray[index++] = nums[index1++];
        while (index2 <= endIndex)
            newArray[index++] = nums[index2++];
        for (int i = 0; i < length; i++)
            nums[startIndex + i] = newArray[i];
    }
}

All Problems

All Solutions