跳到主要内容

数组逆序对

题一、数组中的逆序对​

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

示例1:

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

方案A、归并排序​

预备知识: 归并排序是分治思想的典型应用，它包含这样三个步骤:

  • 分解: 待排序的区间为 [l, r], 令 m = (l+r) / 2 , 我们把 [l,r] 分成 [l,m] 和 [m+1,r]

  • 解决: 使用归并排序递归地排序两个子序列

  • 合并: 把两个已经排好序的子序列[l,m] 和 [m+1,r] 合并起来

在待排序序列长度为1的时候，递归开始回升,因为我们默认长度为1的序列是排好序的

思路: 那么求逆序对和归并排序又有什么关系呢？关键就在于归并当中并的过程。假设我们有两个已排序的序列等待合并,分别是 L={8,12,16,22,100} 和 R={9,26,55,64,91}。一开始我们用指针 lPtr = 0 指向 L 的首部，rPtr = 0 指向 R 的头部。记已经合并好的部分为 M

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = []
     |                          |
   lPtr                       rPtr

我们发现lPtr指向的元素小于rPtr指向的元素，于是把lPtr指向的元素放入答案，并把 lPtr后移一位。

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = [8]
        |                       |
      lPtr                     rPtr

这个时候我们把左边的 8 加入了答案，我们发现右边没有数比 8 小，所以 8 对逆序对总数的「贡献」为 0。

接着我们继续合并，把 9 加入了答案，此时 lPtr 指向 12，rPtr 指向 26。

L = [8, 12, 16, 22, 100]   R = [9, 26, 55, 64, 91]  M = [8, 9]
        |                          |
       lPtr                       rPtr

此时 lPtr 比 rPtr 小，把 lPtr 对应的数加入答案，并考虑它对逆序对总数的贡献为 rPtr 相对 R 首位置的偏移 1（即右边只有一个数比 12 小，所以只有它和 12 构成逆序对），以此类推。

我们发现用这种「算贡献」的思想在合并的过程中计算逆序对的数量的时候，只在 lPtr 右移的时候计算，是基于这样的事实：当前 lPtr 指向的数字比 rPtr 小，但是比 R 中 [0 ... rPtr - 1] 的其他数字大，[0 ... rPtr - 1] 的其他数字本应当排在 lPtr 对应数字的左边，但是它排在了右边，所以这里就贡献了 rPtr 个逆序对。

实现

function mergeAndCount(nums, left, middle, right, temp) {
  for (let i = left; i <= right; i++) {
    temp[i] = nums[i];
  }
  let i = left;
  let j = middle + 1;
  let count = 0;
  for (let k = left; k <= right; k++) {
    if (i === middle + 1) {
      nums[k] = temp[j];
      j++;
    } else if (j === right + 1) {
      nums[k] = temp[i];
      i++;
    } else if (temp[i] <= temp[j]) {
      nums[k] = temp[i];
      i++;
    } else {
      nums[k] = temp[j];
      j++;
      count += middle - i + 1;
    }
  }
  return count;
}
function reversePairsImpl(nums, left, right, temp) {
  if (left === right) {
    return 0;
  }
  let middle = (left + right) >> 1;
  let leftPairs = reversePairsImpl(nums, left, middle, temp);
  let rightPairs = reversePairsImpl(nums, middle + 1, right, temp);
  if (nums[middle] <= nums[middle + 1]) {
    return leftPairs + rightPairs;
  }
  let crossPairs = mergeAndCount(nums, left, middle, right, temp);
  return leftPairs + rightPairs + crossPairs;
}
function reversePairs(nums) {
  let length = nums.length;
  if (length < 2) {
    return 0;
  }
  let copy = [];
  for (let i = 0; i < length; i++) {
    copy[i] = nums[i];
  }
  let temp = [];
  return reversePairsImpl(copy, 0, length - 1, temp);
}