golang中怎么求數(shù)組中的逆序?qū)?/h1>

這篇文章將為大家詳細講解有關(guān)golang中怎么求數(shù)組中的逆序?qū)?，文章?nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供竹山網(wǎng)站建設(shè)、竹山做網(wǎng)站、竹山網(wǎng)站設(shè)計、竹山網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計與制作、竹山企業(yè)網(wǎng)站模板建站服務(wù)，10年竹山做網(wǎng)站經(jīng)驗，不只是建網(wǎng)站，更提供有價值的思路和整體網(wǎng)絡(luò)服務(wù)。

在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)?。輸入一個數(shù)組，求出這個數(shù)組中的逆序?qū)Φ目倲?shù)。

 示例 1:

輸入: [7,5,6,4]
輸出: 5

 限制：

0 <= 數(shù)組長度 <= 50000

解題思路

1，本題，首先想到的是暴力解法，提交超時

2，于是想到了歸并，排序

這個題解假設(shè)你已經(jīng)明白歸并排序的原理。

就以arr = [7,5,6,4]這個例子來講解為什么一遍歸并排序就看可以解決逆序?qū)Φ膯栴}。

按照歸并排序的思路，會將arr分解為arrL = [7,5],arrR = [6,4];

繼續(xù)分解為arrLL = [7], arrLR = [5]; arrRL = [6], arrRR = [4];

自此分解完成。

接下來合并：

假設(shè)i為arrLL的數(shù)組下標，j為arrLR的數(shù)組下標, index為新數(shù)組res的下標，初始值都為0

首先arrLL與arrLR合并，因為arrLL[i] > arrLR[j]，

所以可以說明arrLL中7及其之后的所有數(shù)字都大于arrLR中的5，

也就是說7及其之后的所有元素都可以與5組成逆序?qū)Γ?/p>

所以此時7及其之后的所有元素個數(shù)（leftLen - i）即我們要的逆序?qū)?shù)，需要添加到結(jié)果sum中。即sum += leftLen - i

（這也就是此算法高效的地方，一次可以查找到好多次的逆序?qū)?shù)，而且不會重復）

合并之后為arrL=[5,7].

根據(jù)上述方法將arrRL和arrRR合并為arrR=[4,6];

現(xiàn)在將arrL和arrR合并為arr：

5 > 4，說明5及其之后的所有元素都能與4組成逆序?qū)Γ凰詓um += （leftLen - i）；

5 < 6，正常排序，不做處理

7 > 6，說明7及其之后的所有元素都能與6組成逆序?qū)?；所以sum += （leftLen - i）；

7，正常排序，不作處理

代碼實現(xiàn)

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}

關(guān)于golang中怎么求數(shù)組中的逆序?qū)头窒淼竭@里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。


分享題目：golang中怎么求數(shù)組中的逆序?qū)?
文章出自：http://weahome.cn/article/goiejp.html