493 Reverse Pairs

1. Question

Given an arraynums, we call(i, j)an important reverse pair ifi < jandnums[i] > 2*nums[j].
You need to return the number of important reverse pairs in the given array.
Example1:
1
Input: [1,3,2,3,1]
2
3
Output: 2
Copied!
Example2:
1
Input: [2,4,3,5,1]
2
3
Output: 3
Copied!
Note:
  1. 1.
    The length of the given array will not exceed50,000.
  2. 2.
    All the numbers in the input array are in the range of 32-bit integer.

2. Implementation

(1) Merge Sort
1
class Solution {
2
public int reversePairs(int[] nums) {
3
if (nums == null || nums.length == 0) {
4
return 0;
5
}
6
7
int n = nums.length;
8
int[] res = new int[1];
9
mergeSort(nums, 0, n - 1, res);
10
return res[0];
11
}
12
13
public void mergeSort(int[] nums, int start, int end, int[] res) {
14
if (start >= end) {
15
return;
16
}
17
18
int mid = start + (end - start) / 2;
19
mergeSort(nums, start, mid, res);
20
mergeSort(nums, mid + 1, end, res);
21
22
int count = 0;
23
int left = start, right = mid + 1;
24
25
while (left <= mid) {
26
if (right <= end && (nums[left] > 2 * (long)nums[right])) {
27
++count;
28
++right;
29
}
30
else {
31
res[0] += count;
32
++left;
33
}
34
}
35
merge(nums, start, mid, end);
36
}
37
38
public void merge(int[] nums, int start, int mid, int end) {
39
int[] temp = new int[end - start + 1];
40
41
int i = start;
42
int j = mid + 1;
43
int k = 0;
44
45
while (i <= mid && j <= end) {
46
if (nums[i] < nums[j]) {
47
temp[k++] = nums[i++];
48
}
49
else {
50
temp[k++] = nums[j++];
51
}
52
}
53
54
while (i <= mid) {
55
temp[k++] = nums[i++];
56
}
57
58
while (j <= end) {
59
temp[k++] = nums[j++];
60
}
61
62
for (int m = start; m <= end; m++) {
63
nums[m] = temp[m - start];
64
}
65
}
66
}
Copied!

3. Time & Space Complexity

Merge Sort:时间复杂度O(nlogn), 空间复杂度O(n)