数据结构与算法

【算法-数组】获取数组中逆序对的数量

Posted by Gemicat on January 9, 2020

题目

输入一个数组, 求出这个数组中的逆序对的总数。

逆序对：在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对

样例

输入：[7, 5, 6, 4]

输出：5 // (7,5), (7,6), (7,4), (5,4), (6,4)

传送门：数组中的逆序对

解题

思路1：暴力破解法

看到这道题，最简单直接的就是两层循环暴力破解，但是它的有点和缺点也很明显。

  1. 优点：代码简单，思路清晰，出错概率低。
  2. 缺点：时间复杂度 O(n^2)
function solution(arr) {
  var length = arr.length
  var num = 0
  for (var i = 0; i < length; i++) {
    for (var j = i + 1; j < length; j++) {
      arr[i] > arr[j] && num++
    }
  }
  return num
}

思路2：分治法

既然是要考虑更优的方案，可以考虑查找逆序对是如何进行判断的，就是比较当前值和后面值的大小，那么在排序算法中也是会对所有值的大小进行比较，那么是否可以用一种排序算法来处理？

分治法：

即分而治之，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

分治法的特征：

  1. 问题缩小到一定规模容易解决 (大多数问题都能满足);
  2. 分解成的子问题是相同种类的子问题，即该问题具有最优子结构性质 (递归);
  3. 分解而成的小问题在解决之后要可以合并 (关键);
  4. 子问题是相互独立的，即子问题之间没有公共的子问题 (如果不满足，也可以分治，但是会有大量重复子问题被多次计算，拖慢了算法效率);

可以看到，获取逆序对问题，其实就是将数组缩小到两个值之间比较，将比较后的结果汇总就是逆序对的个数，符合分治法的条件，那么使用分治法下的 归并排序 的思路考虑下问题。

归并排序图解：

image

思路分析：

归并排序过程中，会不断的对两个有序数组进行比较，那么准备两个指针指向两个数组最后的元素，当左面的指针元素大于右面指针对应的元素，那么从左指针到右指针中间的元素都是逆序的。

步骤如下：

graph TD
A[7, 5, 6, 4] --> B[7, 5]
A[7, 5, 6, 4] --> C[6, 4]
B[7, 5] ==排序,左侧数字大于右侧,逆序+1==> D[5, 7]
C[6, 4] ==排序,左侧数字大于右侧,逆序+1==> E[4, 6]
D[5, 7] --> F[两个数组进行排序, 7 > 4,6, 逆序+2, 然后 5 > 4 逆序 + 1]
E[4, 6] --> F[两个数组进行排序, 7 > 4,6, 逆序+2, 然后 5 > 4 逆序 + 1]
F[两个数组进行排序, 7 > 4,6, 逆序+2, 然后 5 > 4 逆序 + 1] --> G[4, 5, 6, 7]
  1. 优点: 时间复杂度为 O(nlogn)
  2. 缺点：会对原数组进行修改；需要额外的辅助空间；

代码实现：

function solution (arr, start, end) {
  if (end <= 0 || start === end) {
    return 0
  }

  const copy = new Array(end - start + 1)
  const length = (end - start) >> 1 // 中间数字
  const leftNum = solution(arr, start, start + length)
  const rightNum = solution(arr, start + length + 1, end)

  let i = start + length // 左子数组的最后一个下标
  let j = end // 右子数组的最后一个下标
  let count = leftNum + rightNum
  let copyIndex = end - start // copy数组中的最后一个下标

  for (; i >= start && j >= start + length + 1;) {
    if (arr[i] > arr[j]) {
      copy[copyIndex--] = arr[i--]
      count += j - start - length
    } else {
      copy[copyIndex--] = arr[j--]
    }
  }

  // 左、右其中一个数组空了后，将剩余数字依次放入临时数组内
  for (; i >= start; --i) {
    copy[copyIndex--] = arr[i]
  }
  for (; j >= start + length + 1; --j) {
    copy[copyIndex--] = arr[j]
  }

  // 将排序号的数据放到原数组中
  for (i = 0; i < end - start + 1; ++i) {
    arr[i + start] = copy[i]
  }

  // clear
  copy.length = 0

  return count
}

const arr = [7, 5, 6, 4]
solution(arr, 0, arr.length - 1) // output: 5

其他思路

这道题还可以用 BST，树状数组，线段树及其他方式解出

参考资料：