2021-03-09:在一个数组中,一个数左边比它小的数的总和,叫数的小和,所有数的小和累加起来,叫数组小和。求数组小和。例子: [1,3,4,2,5],1左边比1小的数:没有,3左边比3小的数:1,4左边比4小的数:1、3,2左边比2小的数:1,5左边比5小的数:1、3、4、 2,所以数组的小和为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 } //求中点 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 { //辅助数组 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++ } //辅助数组拷贝到原数组 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 } //求中点 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] } //辅助数组 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++ } //辅助数组拷贝到原数组 copy(arr[L:R+1], help) return ans }
执行结果如下: