溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關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:=0for 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)/2sl,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:=0l:=len(a)r:=len(b)all:=make([]int,l+r)i:=0j:=0index:=0for ;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中怎么求數組中的逆序對就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
