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：在一个数组中，对于每个数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

}

执行结果如下：

---

左神java代码

力扣493. 翻转对

评论

2021-03-07：在一个数组中，对于每个数num，求有多少个后面的数 * 2 依然<num，求总个数。比如：[3,1,7,0,2]，3的后面有：1，0；1的后面有：0；7的后面有：0，2；0的后面没有；2的后面没有；所以总共有5个。的相关教程结束。