-
Notifications
You must be signed in to change notification settings - Fork 23
/
Copy path0493-reverse-pairs.js
59 lines (55 loc) · 1.34 KB
/
0493-reverse-pairs.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* 493. Reverse Pairs
* https://leetcode.com/problems/reverse-pairs/
* Difficulty: Hard
*
* 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].
*/
/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function(nums) {
let count = 0;
mergeSort(nums, 0, nums.length - 1);
return count;
function mergeSort(input, left, right) {
if (left >= right) return;
const middle = Math.floor((left + right) / 2);
mergeSort(input, left, middle);
mergeSort(input, middle + 1, right);
merge(input, left, middle, right);
}
function merge(input, left, middle, right) {
let j = middle + 1;
for (let i = left; i <= middle; i++) {
while (j <= right && input[i] > 2 * input[j]) {
j++;
}
count += j - (middle + 1);
}
const order = [];
let i = left;
j = middle + 1;
while (i <= middle && j <= right) {
if (input[i] <= input[j]) {
order.push(input[i++]);
} else {
order.push(input[j++]);
}
}
while (i <= middle) {
order.push(input[i++]);
}
while (j <= right) {
order.push(input[j++]);
}
for (let k = 0; k < order.length; k++) {
input[left + k] = order[k];
}
}
};