493 Reverse Pairs
493. Reverse Pairs
1. Question
Given an arraynums
, we call(i, j)
an important reverse pair ifi < j
andnums[i] > 2*nums[j]
.
You need to return the number of important reverse pairs in the given array.
Example1:
Input: [1,3,2,3,1]
Output: 2
Example2:
Input: [2,4,3,5,1]
Output: 3
Note:
The length of the given array will not exceed
50,000
.All the numbers in the input array are in the range of 32-bit integer.
2. Implementation
(1) Merge Sort
class Solution {
public int reversePairs(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int n = nums.length;
int[] res = new int[1];
mergeSort(nums, 0, n - 1, res);
return res[0];
}
public void mergeSort(int[] nums, int start, int end, int[] res) {
if (start >= end) {
return;
}
int mid = start + (end - start) / 2;
mergeSort(nums, start, mid, res);
mergeSort(nums, mid + 1, end, res);
int count = 0;
int left = start, right = mid + 1;
while (left <= mid) {
if (right <= end && (nums[left] > 2 * (long)nums[right])) {
++count;
++right;
}
else {
res[0] += count;
++left;
}
}
merge(nums, start, mid, end);
}
public void merge(int[] nums, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int i = start;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= end) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
}
else {
temp[k++] = nums[j++];
}
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= end) {
temp[k++] = nums[j++];
}
for (int m = start; m <= end; m++) {
nums[m] = temp[m - start];
}
}
}
3. Time & Space Complexity
Merge Sort:时间复杂度O(nlogn), 空间复杂度O(n)
Last updated
Was this helpful?