剑指Offer题解 - Day69
剑指 Offer 51. 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
「示例 1:」
输入: [7,5,6,4]
输出: 5
「限制：」
0 <= 数组长度 <= 50000
分析：
首先考虑使用暴力法求解。思路是进行双层遍历，然后判断外层的值大于内层的值时，累加器递增，最终返回累加器变量即可。
/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function(nums) {
let count = 0;
for (let i = 0; i < nums.length; i++) {
for (let j = i; j < nums.length; j++) {
if (nums[i] > nums[j]) count++;
}
}
return count;
};
该方法浅显易懂，但是由于数组长度最大是50000，因此该方法会超时，本题不适合采用双层遍历。
那么如何降低时间复杂度呢？最好是一次遍历就可以找出所有的逆序对。
归并排序
可以借用归并的思想进行题解。当进行合并的时候，可以通过判断左右子数组内元素的大小关系，来统计最终的逆序对个数。
具体代码如下：
/**
* @param {number[]} nums
* @return {number}
*/
var reversePairs = function(nums) {
const length = nums.length;
let temp = Array.from({ length }); // 临时数组，存储合并时候的左右子数组
const mergeSort = (l, r) => {
if (l >= r) return 0; // 单个元素，递归终止
let m = Math.floor((l + r) / 2); // 寻找中间元素，进行划分
let res = mergeSort(l, m) + mergeSort(m + 1, r); // 继续拆分左右子数组
// 合并阶段
let i = l; // 左子数组的首位元素索引
let j = m + 1; // 右子数组的首位元素索引
for (let k = l; k <= r; k++) {
temp[k] = nums[k]; // 将左右子数组的元素缓存起来
}
for (let k = l; k <= r; k++) { // 将较小元素按顺序放入原数组相对位置
if (i === m + 1) nums[k] = temp[j++];
else if (j === r + 1 || temp[i] <= temp[j]) nums[k] = temp[i++];
else {
nums[k] = temp[j++];
res += m - i + 1;
}
}
return res;
}
return mergeSort(0, length - 1);
};
- 时间复杂度 O(nlogn)。
- 空间复杂度 O(n)。
分析：
具体的代码逻辑，注释里已经写得很清楚了。具体来看第二次循环的相关逻辑。
这里主要是合并阶段，将左右子数组的元素进行逐个比较，哪个元素小就将元素放入原数组指定位置。这也告诉我们，归并排序是原地排序。
如果左子数组的索引超出了左子数组，意味着左子数组的元素已经排序到原数组中了，这时只需要将右子数组的元素逐个放入原数组即可。同理，当右子树组的索引超出了右子树组，只需要将左子数组的元素逐个放入原数组即可。
如果左子数组的元素小于等于右子树组的元素，将左子树组的元素放入原数组。否则，意味着左边大右边小，这时就需要右子树组的元素放入原数组。此时就符合前面元素大于后面元素，可以形成逆序对。
而当前状态下逆序对的个数为m - i + 1 。具体是怎么算出来的呢？是因为左子数组此时是有序的，右子树组此时也是有序的，如果说当前左边大于右边，也就是说，在左子数组中，当前元素及以后所有的元素都会大于右边的当前元素。因此需要将右子树组的首位索引减去当前左元素的索引。
当前递归需要返回最终累加的res结果。这样可以在回溯时不断进行累加，最终得到所有的逆序对。
总结
本题采用归并排序的方法求得逆序对的个数。难度系数困难。核心逻辑在于合并时计算逆序对的个数。
归并排序的时间复杂度是O(nlogn) ，而维护临时数组需要占用O(n) 的空间。
腾讯云开发者
