2021-03-07:在一个数组中,对于每个数num,求有多少个后面的数 * 2 依然<num,求总个数。比如:[3,1,7,0,2],3的后面有:1,0;1的后面有:0;7的后面有:0,2;0的后面没有;2的后面没有;所以总共有5个。
福哥答案2021-03-07:
归并排序模板。有代码。
代码用golang编写,代码如下:
package main import "fmt" func main() { arr := []int{3, 1, 7, 0, 2} ret := BiggerTwice(arr) fmt.Println(ret) } func BiggerTwice(arr []int) int { arrLen := len(arr) if arrLen <= 1 { return 0 } return process(arr, 0, arrLen-1) } func process(arr []int, L int, R int) int { curLen := R - L + 1 if curLen <= 1 { return 0 } //求中点 M := L + (R-L)>>1 return process(arr, L, M) + process(arr, M+1, R) + merge(arr, L, M, R) } func merge(arr []int, L int, M int, R int) int { //新增的代码 ans := 0 windowR := M + 1 for i := L; i <= M; i++ { for windowR <= R && (arr[i] > arr[windowR]*2) { windowR++ } ans += windowR - M - 1 } //辅助数组 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 }
执行结果如下: