LeetCode-in-Java
493. Reverse Pairs
Hard
Given an integer array nums, return the number of reverse pairs in the array.
A reverse pair is a pair (i, j) where 0 <= i < j < nums.length and nums[i] > 2 * nums[j].
Example 1:
Input: nums = [1,3,2,3,1]
Output: 2
Example 2:
Input: nums = [2,4,3,5,1]
Output: 3
Constraints:
1 <= nums.length <= 5 * 104-231 <= nums[i] <= 231 - 1
Solution
import java.util.Arrays;
public class Solution {
public int reversePairs(int[] nums) {
return mergeSort(nums, 0, nums.length - 1);
}
private int mergeSort(int[] nums, int start, int end) {
if (start >= end) {
return 0;
}
int mid = start + (end - start) / 2;
int cnt = mergeSort(nums, start, mid) + mergeSort(nums, mid + 1, end);
int j = mid + 1;
for (int i = start; i <= mid; i++) {
// it has to be 2.0 instead of 2, otherwise it's going to stack overflow, i.e. test3 is
// going to fail
while (j <= end && nums[i] > nums[j] * 2.0) {
j++;
}
cnt += j - (mid + 1);
}
Arrays.sort(nums, start, end + 1);
return cnt;
}
}