小和問(wèn)題：在一個(gè)數(shù)組中，每一個(gè)數(shù)左邊比當(dāng)前數(shù)小的數(shù)累加起來(lái)，叫做這個(gè)數(shù)組的小和，求一個(gè)數(shù)組的小和

例子：

［1，3，4，2，5］

1－> 1

3－> 1

4 －> 1，3

5 －> 1，3，4，2

1+? ?1+?3+? ?1? ?+1+3+4+2 ＝ 16

此問(wèn)題可以轉(zhuǎn)化為當(dāng)前值右側(cè)有幾個(gè)比當(dāng)前值大，比較大的個(gè)數(shù) * 當(dāng)前值 求和，如：

1? －> 3,4,2,5? ?4*1

3? －> 4,5? ? ? ? ?2*2

4? －> 5? ? ? ? ? ?1*4

2? －> 5? ? ? ? ? ?1*2

import syssys.setrecursionlimit(10000)def mergeSort(L,l,r): if l == r:return 0mid = int(l + ((r-l)>>1))return mergeSort(L,l,mid) + mergeSort(L,mid+1,r) + merge(L,l,mid,r)def merge(L,l,m,r):help_ = [0] * (r-l+1)i = 0p1 = lp2 = m + 1res = 0while p1 <= m and p2 <= r:if L[p1] < L[p2]:res += (r-p2+1)*L[p1]help_[i] = L[p1]i +=1p1 +=1else:help_[i] = L[p2]i +=1p2 +=1while p1 <= m:help_[i] = L[p1]i +=1p1 +=1while p2 <= r:help_[i] = L[p2]i +=1p2 +=1for i in range(len(help_)):L[l+i] = help_[i]return resmergeSort([1,3,4,2,5],0,4)

?

?

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的小和问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。