查找使i<j和A[i] >= 2 A[j]的对数(i，j)

Question

问题是找到一个算法(最好使用分而治之的方法)来计算i= 2*Aj数组中所有有序对(i，j)的数目。

我已经知道一个O(2)方式，但我想要一个更有效的算法或日志顺序。

这是我在python中的代码：

ans = 0

def recursion(arr):
    global ans
    if len(arr) > 1:
        left = arr[:len(arr)//2]
        right = arr[len(arr)//2:]
        recursion(left)
        recursion(right)
        for i in left:
            for j in right:
                if i >= 2*j:
                    ans += 1

a = list(map(int, input().split()))
recursion(a)
print(ans)

样本输入: 8，1，9 ,4，1

预期产出:6

Answer 1

通过对每个数组的一半排序和调整合并/倒排计数的逻辑，可以使代码的征服部分更有效地工作。下面的Python代码利用Timsort生成一个线性时间排序的合并。

顺便说一句，我在给定的输入中计算了6个这样的对：(8, 1), (8, 4), (8, 1), (9, 4), (9, 1), (4, 1)。

def merge(left, right):
    return sorted(left + right)


def recursion(arr):
    if len(arr) <= 1:
        return 0, arr
    half = len(arr) // 2
    left_ans, left = recursion(arr[:half])
    right_ans, right = recursion(arr[half:])
    cross_ans = 0
    j = 0
    for i in range(len(left)):
        while j < len(right) and left[i] >= 2 * right[j]:
            j += 1
        cross_ans += j
    return left_ans + cross_ans + right_ans, merge(left, right)


print(recursion([8, 1, 9, 4, 1])[0])