题目描述

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

限制：

0 <= 数组长度 <= 50000

用例

示例 1:

• 输入: [7,5,6,4]
• 输出: 5

思路

通过归并排序实现，图是使用的anaela的题解 (opens new window)

归并排序一般的整个过程如下图所示：

归并排序中合并的过程大致如下图所示 —— 两者比较的时候就是比较逆序对的时间 —— 当右比左大时，就存在逆序对了

、

借用下面一张图把上面两个过程整合起来

代码实现

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入nums: ");
var nums = readline().split(",").map(Number);

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function (nums) {
  // 统计逆序对
  // 1 2 3 4 5
  let cnt = 0;

  if (nums.length < 2) {
    return cnt;
  }
  const mergeSort = (leftIndex, rightIndex) => {
    if (leftIndex === rightIndex) {
      // 返回只有一个元素的数组
      return [nums[leftIndex]];
    }
    let mid = leftIndex + Math.floor((rightIndex - leftIndex) / 2);
    // 左边包含中间元素
    let left = mergeSort(leftIndex, mid);
    let right = mergeSort(mid + 1, rightIndex);

    // 用来存储排序后的数组
    let arr = new Array(rightIndex - leftIndex + 1).fill(0);

    // 合并时的三个指针
    let cur = 0,
      l = 0,
      r = 0;
    while (l < left.length && r < right.length) {
      // 开始比较
      // 左比右小，就把左放入arr
      // 此时不存在逆序对
      if (left[l] <= right[r]) {
        arr[cur] = left[l];
        cur++;
        l++;
      } else {
        // 右比左小，就把右放入arr
        // 此时就存在逆序对了，要更新cnt
        // 更新规则 —— 因为右比当前的左小了，而左数组又是排好序的
        // 所以此刻的右数比当前左数包括当前这个数到左数组结尾的值都要小
        // 这些都是逆序对的个数 —— left.length - l
        arr[cur] = right[r];
        cur++;
        r++;
        cnt += left.length - l;
      }
    }
    // 谁还没放完就把剩下的放到arr
    while (l < left.length) {
      arr[cur] = left[l];
      cur++;
      l++;
    }
    while (r < right.length) {
      arr[cur] = right[r];
      cur++;
      r++;
    }
    return arr;
  };
  const arr = mergeSort(0, nums.length - 1);
  console.log("arr: ", arr);
  return cnt;
};

const res = reversePairs(nums);
console.log("结果为: ", res);

/* 
  请输入nums:
  7,5,6,4
  arr:  [ 4, 5, 6, 7 ]
  结果为:  5
*/