剑指offer数组中的逆序对JavaScript

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

解法 1: 暴力法（TLE）

直接双重循环，挨个检查能否为逆序对。代码实现比较简单：

/** * @param {number[]} nums * @return {number} */var reversePairs = function(nums) { let res = 0; const length = nums.length; for (let i = 0; i nums[j] && ++res; } } return res;};

时间复杂度是。在 leetcode 上会 TLE，无法通过（毕竟这是道标注「困难」的题目）。

解法 2: 归并排序（正确解法）

这题的正确解法是要借助归并排序的思路，在归并的过程中，快速统计逆序对。这种解法比较难想到，但是应用归并排序的题目真的不多，所以这题很有研究和收藏意义。

核心的处理逻辑都封装在 findInversePairNum 函数中。它的职能就是统计数组arr[start, end]范围中的逆序对，并且统计完后，arr[start, end]范围中的元素会被排序（这点和归并排序的过程一样）。

那么函数又是如何快速统计逆序对的呢？大体过程如下：

• 递归调用，拿到左子数组和右子数组的逆序对（此时，左子数组和右子数组也都排序完成了）
• 指针 i 和 j 分别指向左子数组和右子数组的最右侧，此时会有 2 种情况：
  • arr[i] > arr[j]：那么说明arr[i]大于右子数组中所有元素，逆序对添加j - start - length，向左边移动指针 i
  • arr[i] <= arr[j]: 对arr[i]来说，不存在逆序对，向左边移动指针 j
• i 和 j 遍历完各自数组后，最后返回逆序对之和就可

代码实现如下：

// ac地址：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/// 原文地址：https://xxoo521.com/2020-03-12-reverse-pairs//** * @param {number[]} nums * @return {number} */var reversePairs = function(nums) { return findInversePairNum(nums, 0, nums.length - 1);};/** * @param {number[]} arr * @param {number} start * @param {number} end */function findInversePairNum(arr, start, end) { if (start >= end) return 0; const copy = new Array(end - start + 1); const length = Math.floor((end - start) / 2); // 左数组长度 const leftNum = findInversePairNum(arr, start, start + length); const rightNum = findInversePairNum(arr, start + length + 1, end); let i = start + length; let j = end; let copyIndex = end - start; let num = 0; while (i >= start && j >= start + length + 1) { if (arr[i] > arr[j]) { num += j - start - length; copy[copyIndex--] = arr[i--]; } else { copy[copyIndex--] = arr[j--]; } } while (i >= start) { copy[copyIndex--] = arr[i--]; } while (j >= start + length + 1) { copy[copyIndex--] = arr[j--]; } for (let k = start; k <= end; ++k) { arr[k] = copy[k - start]; } return num + leftNum + rightNum;}

时间复杂度是，空间复杂度是。假如还是觉得不好了解，可以以数组 7、5、6、4 为例，按照前面过程，手动计算一下。

更多资料

整理不易，若对您有帮助，请给个「关注+点赞」，您的支持是我升级的动力 ??

• ??Blog：剑指 Offer 题解 + JS 代码
• ??Github ： dongyuanxin/blog
• ?? 公众号：心谭博客