翻转对

[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
};