数组中的逆序对

发表于 | 分类于

说明

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

1
2
输入: [7,5,6,4]
输出: 5

算法

归并排序分治法

在合并的过程中统计逆序对

  • 升序/降序逻辑都可以
  • 相同元素不是逆序对大于才是
  • 升序
    从最小开始比较，谁的第一个元素最小就谁就是基准（不是绝对的left或right)，如果遇到相同元素，则要先去掉非基准数组相同元素
    以右边数组为基准，但是对于重复元素，应该消掉左边数组的元素
  • 降序
    以左边数组为基准，但是对于重复元素，应该消掉右边数组元素
    如：[3，2，1]，[3，1]

  • 降序逻辑实现
    从最大开始比较，谁的第一个元素最大就谁就是基准（不是绝对的left或right)，如果遇到相同元素，则要先去掉非基准数组相同元素

    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
    var reversePairs = function (num) {
        const sumObj = {count:0};
        const newArr = helper(num, 0, num.length - 1,sumObj);
        return sumObj.count;
    };

    function helper(num, lo, hi,sumObj) {
        if (lo >= hi) {
            return [num[lo]]
        }
        let mid = lo + Math.floor((hi - lo) / 2);
        let leftSorted = helper(num, lo, mid,sumObj);
        let rightSorted = helper(num, mid + 1, hi,sumObj);
        return merge(leftSorted, rightSorted,sumObj);
    }
    //[1,8],[2,9]
    function merge(aNum, bNum,sumObj) {
        let res = [];
        while (aNum.length && bNum.length) {
            //这里决定了用哪个（比较的是第一个元素）
            //
            if(aNum[0] > bNum[0]){
                sumObj.count = sumObj.count + bNum.length;
                res.push(aNum.shift());
            //等于的不算逆对，只有大于的才算
            } else if(aNum[0] === bNum[0]){
                res.push(bNum.shift());
            } else {
                res.push(bNum.shift());
            }
        }
        return aNum.length > 0 ? res.concat(aNum) : res.concat(bNum);
    }

  • 升序逻辑实现

    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
    /**
     * @param {number[]} nums
     * @return {number}
     */
    var reversePairs = function (num) {
        const sumObj = {count:0};
        const newArr = helper(num, 0, num.length - 1,sumObj);
        return sumObj.count;
    };

    function helper(num, lo, hi,sumObj) {
        if (lo >= hi) {
            return [num[lo]]
        }
        let mid = lo + Math.floor((hi - lo) / 2);
        let leftSorted = helper(num, lo, mid,sumObj);
        let rightSorted = helper(num, mid + 1, hi,sumObj);
        return merge(leftSorted, rightSorted,sumObj);
    }
    //[1,8],[2,9]
    function merge(aNum, bNum,sumObj) {
        let res = [];
        while (aNum.length && bNum.length) {
            //left小
            if (aNum[0] < bNum[0]) {
                res.push(aNum.shift());
            } else if(aNum[0] === bNum[0]){
                res.push(aNum.shift());
            } else {//right小
                //因为是升序
                sumObj.count = sumObj.count + aNum.length;
                res.push(bNum.shift());
            }
        }
        return aNum.length > 0 ? res.concat(aNum) : res.concat(bNum);
    }

暴力法（超时)

1
2
3
4
5
6
7
8
9
10
11
var reversePairs = function(nums) {
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] > nums[j] ) {
                count++;
            }
        }
    }
    return count;
};