2021-03-09：在一個數(shù)組中，一個數(shù)左邊比它小的數(shù)的總和戳表，叫數(shù)的小和桶至，所有數(shù)的小和累加起來，叫數(shù)組小和匾旭。求數(shù)組小和镣屹。例子： [1,3,4,2,5]，1左邊比1小的數(shù)：沒有价涝，3左邊比3小的數(shù)：1女蜈，4左邊比4小的數(shù)：1、3色瘩，2左邊比2小的數(shù)：1伪窖，5左邊比5小的數(shù)：1、3居兆、4覆山、 2，所以數(shù)組的小和為1+1+3+1+1+3+4+2=16 泥栖。
福哥答案2021-03-09：
1.歸并排序簇宽，從左往右勋篓，相等拷右。有代碼晦毙。
2.歸并排序模板生巡。有代碼。
代碼用golang編寫见妒，代碼如下：
package main
import "fmt"
func main() {
if true {
arr := []int{1, 3, 4, 2, 5}
ret := smallSum1(arr)
fmt.Println("1.從左往右，相等拷右：", ret)
}
if true {
arr := []int{1, 3, 4, 2, 5}
ret := smallSum2(arr)
fmt.Println("2.歸并排序模板：", ret)
}
}
func smallSum1(arr []int) int {
arrLen := len(arr)
if arrLen <= 1 {
return 0
}
return process1(arr, 0, arrLen-1)
}
func process1(arr []int, L int, R int) int {
curLen := R - L + 1
if curLen <= 1 {
return 0
}
//求中點(diǎn)
M := L + (R-L)>>1
return process1(arr, L, M) + process1(arr, M+1, R) + merge1(arr, L, M, R)
}
func merge1(arr []int, L int, M int, R int) int {
//輔助數(shù)組
help := make([]int, R-L+1)
i := 0
p1 := L
p2 := M + 1
//誰小拷貝誰
ans := 0
for p1 <= M && p2 <= R {
if arr[p1] < arr[p2] {
ans += (R - p2 + 1) * arr[p1]
help[i] = arr[p1]
p1++
} else {
help[i] = arr[p2]
p2++
}
i++
}
for p1 <= M {
help[i] = arr[p1]
p1++
i++
}
for p2 <= R {
help[i] = arr[p2]
p2++
i++
}
//輔助數(shù)組拷貝到原數(shù)組
copy(arr[L:R+1], help)
return ans
}
func smallSum2(arr []int) int {
arrLen := len(arr)
if arrLen <= 1 {
return 0
}
return process2(arr, 0, arrLen-1)
}
func process2(arr []int, L int, R int) int {
curLen := R - L + 1
if curLen <= 1 {
return 0
}
//求中點(diǎn)
M := L + (R-L)>>1
return process2(arr, L, M) + process2(arr, M+1, R) + merge2(arr, L, M, R)
}
func merge2(arr []int, L int, M int, R int) int {
//新增的代碼
ans := 0
windowR := M + 1
for i := M; i >= L; i-- {
for windowR >= M+1 && arr[i] < arr[windowR] {
windowR--
}
ans += (R - windowR) * arr[i]
}
//輔助數(shù)組
help := make([]int, R-L+1)
i := 0
p1 := L
p2 := M + 1
//誰小拷貝誰
for p1 <= M && p2 <= R {
if arr[p1] <= arr[p2] {
help[i] = arr[p1]
p1++
} else {
help[i] = arr[p2]
p2++
}
i++
}
for p1 <= M {
help[i] = arr[p1]
p1++
i++
}
for p2 <= R {
help[i] = arr[p2]
p2++
i++
}
//輔助數(shù)組拷貝到原數(shù)組
copy(arr[L:R+1], help)
return ans
}
執(zhí)行結(jié)果如下：
在這里插入圖片描述
