In this Leetcode Reverse Pairs problem solution 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].
Problem solution in Python.
import bisect class Solution: def reversePairs(self, nums: List[int]) -> int: count,l=0,[] for i in nums : a=bisect.bisect_right (l,i*2)#finding the index count+=len (l)-a#finding the number of greater than equal to i*2 idx=bisect.bisect(l,i)#finding the index where the i need to be inserted l[idx:idx]=[i]#trick for inserting at idx much faster than insert() return count
Problem solution in Java.
class Solution { public int reversePairs(int[] nums) { return mergeSort(nums, 0, nums.length - 1); } private int mergeSort(int[] nums, int l, int r) { if (l >= r) return 0; int count = 0; int mid = l + (r - l) / 2; count += mergeSort(nums, l, mid); count += mergeSort(nums, mid + 1, r); count += merge(nums, l, mid, r); return count; } private int merge(int[] nums, int l, int mid, int r) { int count = 0, l1 = l, l2 = mid + 1, idx = 0; while (l1 <= mid && l2 <= r) { if ((long) nums[l1] > (long) 2 * nums[l2]) { count += mid - l1 + 1; l2++; } else l1++; } l1 = l; l2 = mid + 1; int[] copy = new int[r - l + 1]; while (l1 <= mid && l2 <= r) { if (nums[l1] > nums[l2]) copy[idx++] = nums[l2++]; else copy[idx++] = nums[l1++]; } while (l1 <= mid) copy[idx++] = nums[l1++]; while (l2 <= r) copy[idx++] = nums[l2++]; System.arraycopy(copy, 0, nums, l, r - l + 1); return count; } }
Problem solution in C++.
class Solution {
public:
int reversePairs(vector<int>& nums) {
multiset<long long> tb;
int ret = 0;
int n = nums.size();
for(int i = n - 1; i >= 0; --i) {
long long cur = nums[i];
auto iter = lower_bound(tb.begin(), tb.end(), cur);
ret += distance(tb.begin(), iter);
tb.insert(2 * cur);
}
return(ret);
}
};