网络异常，图片无法展示
|
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4] 输出: 5 复制代码
限制：
0 <= 数组长度 <= 50000
解题思路
本题最简单的一个解题思路就是直接一个双层循环，然后保证内层元素的下标大于外层元素，如果外层元素大于内层元素，则组成一个逆序对，记录数量。双层循环完成，就得到了所有的逆序对。
这样的一个解题思路没有问题，但是提交后会发现超出时间限制，也是就 O(n²) 的时间复杂度是不满足本题要求的。
那还有什么更高效的方式可以解题呢？
这里我们可以利用归并排序解决本题。因为归并排序的回溯过程中，会进行左右数组的组合，当此时选择到的是右侧数组中的元素的时候，如果左侧数组中有未处理的元素，因为前后位置上，左侧数组的元素都在右侧数组元素之前，又因为此时左侧未处理元素值都比当前元素值大，所以此时左侧数组中每一个未处理的元素都与当前元素组成一个逆序对，记录这样的逆序对的数量，当归并排序回溯完成，就得到了数组中所有逆序对的数量。
动画演示
网络异常，图片无法展示
|
代码实现
var reversePairs = function(nums) { // 获取数组长度 const len = nums.length, // 根据输入数组长度，创建额外存储区暂存区间排序结果 arr = Array(len); // 归并排序 并返回逆序对数量 function getCount(l,r){ // 如果当前区间中元素数量小于等于1，则返回0 if(l>=r) return 0; // 获取中间下标，拆分左右子区间 const mid = (l+r)>>1; // 初始化区间中逆序对数量为0 let res = 0; // 获取左区间逆序对数量 res += getCount(l,mid); // 获取右区间逆序对数量 res += getCount(mid+1,r); // 回溯组合过程 let k = l,i = l,j = mid+1; while(i<=mid || j<=r){ if(j>r || (i<=mid && nums[i]<=nums[j])){ arr[k++] = nums[i++] }else{ // 如果此时放入的是右侧数组的元素，当前左侧数组中未处理的元素都与当前元素组成逆序对 arr[k++] = nums[j++] res += mid-i+1 } } // 将排序后的结果更新到原数组 for(let i = l;i<=r;i++){ nums[i] = arr[i] } return res; } // 返回归并排序后的返回值 return getCount(0,len-1) }; 复制代码
至此我们就完成了 leetcode-剑指 Offer 51-数组中的逆序对
如有任何问题或建议，欢迎留言讨论！
