翻转对

[Cosen95]

翻转对：https://leetcode-cn.com/problems/reverse-pairs/

[Cosen95]

思路分析

说实话，起初我能想到的就是暴力法（两层for循环）

简单demo测试可以通过，但是提交时显示超时，显然这种方法似乎不可取

然后看了大佬的题解

用的是归并排序，但现在也不是很明白。。。。

代码解析

暴力法（两层for循环）

/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function(nums) {
let count = 0
let len = nums.length;
for (var i = 0; i < len; i++) {
for (var j = i + 1; j < len; j++) {
if (nums[i] > 2 * nums[j]) {
count++
}
}
}
return count
};

归并排序

/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function(nums) {
let count = 0
let mergeArr = (left, right) => {
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] / 2 > right [j]) {
count += left.length - i;
j++
} else {
i++
}
}
return [...left, ...right].sort((a, b) => a - b)
}
let mergeSort = (arr) => {
if (arr.length <= 1) {
return arr
}
let mid = arr.length >> 1;
let left = arr.slice(0, mid)
let right = arr.slice(mid)
return mergeArr(mergeSort(left), mergeSort(right))
}
mergeSort(nums)
return count
};