时间戳

首页 > 解决方案 > 查找对 (i,j) 的数量，使得 i < j 且 A[i] >= 2A[j]

python - 查找对 (i,j) 的数量，使得 i < j 且 A[i] >= 2A[j]

问题描述

问题是找到一种算法（最好使用分治法）来计算 i < j 且 A[i] >= 2*A[j] 的数组中所有有序对 (i,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

标签： pythonarraysalgorithmdata-structuresbig-o

解决方案

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

推荐阅读