2021-03-07：在一個(gè)數(shù)組中雳旅，對(duì)于每個(gè)數(shù)num，求有多少個(gè)后面的數(shù) * 2 依然<num间聊，求總個(gè)數(shù)攒盈。比如：[3,1,7,0,2]，3的后面有：1哎榴，0型豁；1的后面有：0；7的后面有：0尚蝌，2迎变；0的后面沒(méi)有；2的后面沒(méi)有驼壶；所以總共有5個(gè)氏豌。
福哥答案2021-03-07：
歸并排序模板。有代碼热凹。
代碼用golang編寫(xiě)泵喘，代碼如下：
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
}
//求中點(diǎn)
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
}
//輔助數(shù)組
help := make([]int, R-L+1)
i := 0
p1 := L
p2 := M + 1
//誰(shuí)小拷貝誰(shuí)
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é)果如下：
在這里插入圖片描述
