找出满足 i < j 和 A[i] >= 2A[j] 的对 (i,j) 的数量

Question

问题是找到一种算法（最好使用分而治之的方法）来计算数组中所有有序对 (i,j) 的数量，其中 i < j 且 A[i] >= 2* A[j].

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

这是我在 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

通过对每个数组进行一半排序并调整 mergesort/inversion 计数逻辑，可以使代码的征服部分更有效地工作。下面的 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])

找出满足 i < j 和 A[i] >= 2A[j] 的对 (i,j) 的数量

Find number of pairs (i,j) such that i < j and A[i] >= 2A[j]

python

arrays

algorithm

big-o

data-structures