Problem
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
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 3 > 2 * 1
Example 2:
Input: nums = [2,4,3,5,1]
Output: 3
Explanation: The reverse pairs are:
(1, 4) --> nums[1] = 4, nums[4] = 1, 4 > 2 * 1
(2, 4) --> nums[2] = 3, nums[4] = 1, 3 > 2 * 1
(3, 4) --> nums[3] = 3, nums[4] = 1, 5 > 2 * 1
Constraints:
1 <= nums.length <= 5 * 10^4-2^31 <= nums[i] <= 2^31 - 1
Solution
class Solution {
public int reversePairs(int[] nums) {
int res = mergesort(nums, 0, nums.length - 1);
return res;
}
private int mergesort(int[] nums, int start, int end) {
if (start >= end) {
return 0;
}
int mid = (end - start) / 2 + start;
int res = mergesort(nums, start, mid) + mergesort(nums, mid + 1, end);
for (int i = start, j = mid + 1; i <= mid; i ++) {
while (j <= end && (double)nums[i] / 2.0 > nums[j]) {
j ++;
}
res += j - mid - 1;
}
merge(nums, start, mid, mid + 1, end);
return res;
}
private void merge(int[] nums, int s1, int e1, int s2, int e2) {
int[] result = new int[e2 - s1 + 1];
int i = s1, j = s2, k = 0;
while (i <= e1 || j <= e2) {
int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE;
if (i <= e1) {
a = nums[i];
}
if (j <= e2) {
b = nums[j];
}
if (a < b) {
result[k++] = a;
i ++;
}
else if (a > b){
result[k++] = b;
j ++;
}
else {
if (j == e2 + 1) {
result[k++] = a;
i ++;
}
else {
result[k++] = b;
j ++;
}
}
}
for (k = 0; k < result.length; k ++) {
nums[s1 + k] = result[k];
}
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).