这篇文章将为大家详细讲解有关golang中怎么求数组中的逆序对，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
计算
安全
数据库
网络和加速
企业服务
输入: [7,5,6,4]输出: 5限制：
0 <= 数组长度 <= 50000
解题思路
1，本题，首先想到的是暴力解法，提交超时
2，于是想到了归并，排序
这个题解假设你已经明白归并排序的原理。
就以arr = [7,5,6,4]这个例子来讲解为什么一遍归并排序就看可以解决逆序对的问题。
按照归并排序的思路，会将arr分解为arrL = [7,5],arrR = [6,4];
继续分解为arrLL = [7], arrLR = [5]; arrRL = [6], arrRR = [4];
自此分解完成。
接下来合并：
假设i为arrLL的数组下标，j为arrLR的数组下标, index为新数组res的下标，初始值都为0
首先arrLL与arrLR合并，因为arrLL[i] > arrLR[j]，
所以可以说明arrLL中7及其之后的所有数字都大于arrLR中的5，
也就是说7及其之后的所有元素都可以与5组成逆序对，
所以此时7及其之后的所有元素个数（leftLen - i）即我们要的逆序对数，需要添加到结果sum中。即sum += leftLen - i
（这也就是此算法高效的地方，一次可以查找到好多次的逆序对数，而且不会重复）
合并之后为arrL=[5,7].
根据上述方法将arrRL和arrRR合并为arrR=[4,6];
现在将arrL和arrR合并为arr：
5 > 4，说明5及其之后的所有元素都能与4组成逆序对；所以sum += （leftLen - i）；
5 < 6，正常排序，不做处理
7 > 6，说明7及其之后的所有元素都能与6组成逆序对；所以sum += （leftLen - i）；
7，正常排序，不作处理
代码实现
func reversePairs(nums []int) int { /* sum:=0 for i:=0;i<len(nums)-1;i++{ for j:=i+1;j<len(nums);j++{ if nums[i]>nums[j]{ sum++ } } } return sum */ s,_:=mergeSort(nums) return s}func mergeSort(a []int)(int,[]int){ if len(a)<2{ return 0,a } mid:=len(a)/2 sl,l:=mergeSort(a[:mid]) sr,r:=mergeSort(a[mid:]) s,m:=merge(l,r) //fmt.Println(sl,sr,s,l,r,m) return sl+sr+s,m}func merge(a,b []int)(int,[]int){ sum:=0 l:=len(a) r:=len(b) all:=make([]int,l+r) i:=0 j:=0 index:=0 for ;index<l+r;index++{ if i>=l{ all[index]=b[j] j++ continue } if j>=r{ all[index]=a[i] i++ continue } if a[i]<=b[j]{ all[index]=a[i] i++ continue }else{ all[index]=b[j] //fmt.Println("***",a[i]<=b[j],a[i],b[j],a,b,i,j,all,index) j++ sum+=l-i } }return sum,all}关于golang中怎么求数组中的逆序对就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
原文链接：https://my.oschina.net/u/4586289/blog/4404169
