今天同学在群里分享了一到求逆序对数的题目，LeetCode上搜了一下有道差不多的，那我们来做一下吧。

1. 题目

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

• 示例 1:

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

限制：
0 <= 数组长度 <= 50000

2. 暴力梭哈法

一开始我看到这道题的反应是很简单，直接套上两个循环查喽（题目还是刷的少了2333）。

var reversePairs = function(nums) {
  const length = nums.length
  let count = 0
  for(let i = 0; i < nums.length; i++) {
    for(let l = i + 1; l < nums.length; l++) {
      if(nums[l] < nums[i]) {
        count++
      }
    }
  }
  return count
};

直接就崩了，emmm遇事不决暴力法在这里行不通呀。仔细想想数组长度最大50000，n的二次都快2.5亿次计算了,确实得蹦。

• 分析：

  • 时间复杂度: O(n²)，两个循环，n为数组的长度。
  • 空间复杂度：O(1)，只用到一个临时变量。

3. 归并排序优化

使用归并排序，在合并的过程中处理逆序对数，因为在两个有序的序列里，逆序对得个数是很好算的，
可以看下面两张图

3.1 图一解释归并算法：分而治之的思想

分解 -> 排序 -> 合并

3.2 图二解释取逆序对数

从下图可以看出，每一步的排序中逆序对的个数其实就是

当左边的left[leftIndex] < right[rightIndex]时

$$ 逆序对的个数 = left数组的长度-leftIndex $$

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
  let count = 0 // 记录逆序对数
  const mergeSort = function(nums) {
    const length = nums.length
    if (length < 2) {
      return nums
    }
    const mid = Math.floor((length / 2))   // 获取二分位置
    const leftArr = nums.slice(0, mid)  
    const rightArr = nums.slice(mid)
    return merge(mergeSort(leftArr), mergeSort(rightArr))
  }
  
  const merge = function(leftArr, rightArr) {
    const result = []
    let leftIndex=0,rightIndex=0
    const leftLength = leftArr.length
    const rightLength = rightArr.length
    while(leftIndex < leftLength && rightIndex < rightLength) {
      if(leftArr[leftIndex] <= rightArr[rightIndex]) {
        result.push(leftArr[leftIndex++])
      } else {
        count += (leftLength - leftIndex ) // 关键： 取逆序对的个数
        result.push(rightArr[rightIndex++])
      }
    } 
  
    while(leftIndex < leftLength) {
      result.push(leftArr[leftIndex++])
    }
  
    while(rightIndex < rightLength) {
      result.push(rightArr[rightIndex++])
    }
    return result
  }
  mergeSort(nums)
  return count
};

• 分析：

  • 时间复杂度：同归并排序 O(nlogn)。
  • 空间复杂度：同归并排序 O(n)O(n)，因为归并排序需要用到一个临时数组。

我最后换了很多种写法,想把时空再优化一下，发现都差不多，然后感觉这种是最好理解了。算了就这样吧~~~