可视化图解算法43：数组中的逆序对

1. 题目

​牛客网 面试笔试TOP101    

描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007

数据范围： 对于 50% 的数据, size≤104 对于 100% 的数据, size≤105

数组中所有数字的值满足 0≤val≤1000000

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

输入描述：

题目保证输入的数组中没有的相同的数字

示例1

输入：

[1,2,3,4,5,6,7,0]

返回值：

7

示例2

输入：

[1,2,3]

返回值：

0

2. 解题思路

在解题之前一定要明确题目给定的逆序对的含义：

4对逆序对为：（1,0）、（2,0）、（3,0）和（4,0）。

逆序对的求解可借助归并排序思路完成，即在归并排序中的合并阶段完成逆序对的计算。因此本题的核心是归并排序。

归并排序分为二分与合并两个阶段，具体如下图所示：

• 在合并（排序）阶段的最后一行，由于7与0和并时，为逆序，因此这一行的逆序对为1。

• 在合并（排序）阶段的倒数第二行，由于5、6与0、7和并时，（5,0）、（6,0）构成逆序对，因此这一行的逆序对为2。

• 在合并（排序）阶段的第二行，由于1、2、3、4与0、5、6、7和并时，（1,0）、（2,0）、（3,0）、（4,0）构成逆序对，因此这一行的逆序对为4。

最后将每一行的逆序对累加，即：1+2+4。

关键点：

arr1 [1、2、3、4]与arr2 [0、5、6、7]逆序对求解时，arr1中的元素1与arr2中的元素0构成逆序，由于arr1为有序的（已经排好序了），那么arr1中的元素1之后的元素也与arr2中的元素0构成逆序对。因此逆序对可以这样计算：

len(arr1) - i = 4 - 0 = 4

用数组arr1的长度减去元素1在arr1中所处的位置。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

• Python版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1372589

• Java版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1367845

• Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364843

3. 编码实现

核心代码如下：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param array int整型一维数组* @return int整型*/
var count = 0func InversePairs(array []int) int {// write code hereif len(array) < 2 {return 0}mergeSort(array)return count % 1000000007
}// 归并排序
func mergeSort(array []int) []int {//2. 终止条件：数组的元素个数小于等于1个if len(array) <= 1 {return array}//1.递归步骤//1.1 将数组分为两部分mid := len(array) / 2leftArr := array[:mid]rightArr := array[mid:]//1.2 递归分割，直到不能在分割left := mergeSort(leftArr)right := mergeSort(rightArr)// 1.3. 并（排序）return merge(left, right)
}func merge(left []int, right []int) []int {res := make([]int, 0, len(left)+len(right))i, j := 0, 0n := len(left)// 合并两个切片for i < len(left) && j < len(right) {if left[i] <= right[j] {res = append(res, left[i]) //将左部分的内容追加i++} else {res = append(res, right[j])j++                     //将右部分的内容追加count = count + (n - i) //右部分数据小，需要追加到目标数组中，对应的逆序对为：左部分数组中未比较的长度}}// 如果左侧切片还有剩余元素，将其追加到res中for i < len(left) {res = append(res, left[i])i++}// 如果右侧切片还有剩余元素，将其追加到res中for j < len(right) {res = append(res, right[j])j++}return res
}

具体完整代码你可以参考下面视频的详细讲解。

• Python版本：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372589

• Java版本：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367845

• Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364843

4.小结

数组中逆序对的求解可借助归并排序思路完成，即在归并排序中的合并阶段完成逆序对的计算。

《数据结构与算法》深度精讲课程正式上线啦！七大核心算法模块全解析：

        ✅   链表

        ✅   二叉树

        ✅   二分查找、排序

        ✅   堆、栈、队列

        ✅   回溯算法

        ✅   哈希算法

        ✅   动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss897667807

• Java编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss161443488

• Golang编码实现：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss63997

对于数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：好风凭借力，送我上青云。