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
ac
class Solution {
public int reversePairs(int[] nums) {
// edge cases
if (nums == null || nums.length <= 1) return 0;
int n = nums.length;
int[] bit = new int[n+1];
int[] reverseSorted = new int[n]; // 3,3,2,1,1
int[] copy = Arrays.copyOf(nums, n);
Arrays.sort(copy);
for (int i = 0; i < n; i++) reverseSorted[i] = copy[n-1-i];
int res = 0;
for (int i = 0; i < n; i++) {
res += getSum(bit, getBitIndex(reverseSorted, nums[i] * 2l)-1);
update(bit, getBitIndex(reverseSorted, nums[i]));
}
return res;
}
private int getBitIndex(int[] nums, long val) {
// binary search get first index <= val, because we want to find element > val
int l = 0, r = nums.length-1;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (nums[mid] <= val) r = mid;
else l = mid;
}
int res = nums[l] <= val ? l : nums[r] <= val ? r : r + 1;
return res + 1; // it's actually returning the rank
}
private int getSum(int[] bit, int i) {
int res = 0;
while (i > 0) {
res += bit[i];
i -= i & (-i);
}
return res;
}
private void update(int[] bit, int i) {
while (i < bit.length) {
bit[i]++;
i += i & (-i);
}
}
}
/*
1,3,2,3,1
3,3,2,1,1
2,6,4,6,2
2,4,3,5,1
5,4,3,2,1
4,8,6,10,2
*/
ac2: merge
```java class Solution { int count = 0; public int reversePairs(int[] nums) { // edge cases if (nums == null || nums.length <= 1) return 0;
merge(nums, 0, nums.length-1);
return count;
}
private int[] merge(int[] nums, int start, int end) {
if (start == end) return new int[]{nums[start]};
int mid = start + (end - start) / 2;
int[] left = merge(nums, start, mid);
int[] right = merge(nums, mid+1, end);
int[] res = new int[end - start + 1];
int l = 0, r = 0, i = 0;
int p = 0;
while (l < left.length) {
// extract info
while (p < right.length && right[p] < left[l] / 2.0) p++;
count += p;
// merge process
while (r < right.length && right[r] < left[l]) res[i++] = right[r++];
res[i++] = left[l++];
}
while (r < right.length) res[i++] = right[r++];
return res;
}