golang中怎么求数组中的逆序对
这篇文章将为大家详细讲解有关golang中怎么求数组中的逆序对,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。
创新互联专业为企业提供竹山网站建设、竹山做网站、竹山网站设计、竹山网站制作等企业网站建设、网页设计与制作、竹山企业网站模板建站服务,10年竹山做网站经验,不只是建网站,更提供有价值的思路和整体网络服务。
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
示例 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
for j:=i+1;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
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中怎么求数组中的逆序对就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。
当前标题:golang中怎么求数组中的逆序对
文章源于:http://azwzsj.com/article/goiejp.html