找出数组中差值小于或等于 K 的所有数字

Question

我想找到两个数字A[i]，它们A[j]的差小于或等于K，我需要将这些数字的索引存储在数组 L (Left) R (Right) 中并返回 L & R

def fun(A, k): 

    n = len(A)

    l = 0

    r = n-1

    # traverse the array for the two elements 

    while l<r: 

        if (A[l] - A[r] <= n):

            return A[l],A[r]

        elif (A[l] - A[r] < n): 

            l += 1

        else: 

            r -= 1

    return 0

# Driver code to test above function 

A = [3.5,5,6,12,13] 

k = 1.7

print(fun(A, k))

预期输出：

L[0,0,1,3,3],R[1,2,2,4,4]

Answer 1

您应该使用itertools.combinations获取所有可能的组合，然后测试它们的差异并在需要时追加。from itertools import combinationsdef fun(A, k):&nbsp; &nbsp; l, r = [], []&nbsp; &nbsp; for (x_idx, x_val), (y_idx, y_val) in combinations(enumerate(A), 2):&nbsp; &nbsp; &nbsp; &nbsp; if abs(x_val - y_val) <= k:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; l.append(x_idx)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r.append(y_idx)&nbsp; &nbsp; return l, r测试：A = [3.5,5,6,12,13]&nbsp;k = 1.7print(fun(A, k))# ([0, 1, 3], [1, 2, 4])虽然这不是您的预期输出，但我觉得根据您的逻辑，您的预期输出可能会有一些错误。

Answer 2

O(n log n)在您的示例中利用排序的解决方案A（如果它没有排序，您总是可以支付O(n log n)第二次对其进行排序，尽管保留原始索引可能会使复杂性变得不值得）：from bisect import bisectdef fun(A, k):&nbsp; &nbsp; # Add A.sort() if A not guaranteed to be sorted&nbsp; &nbsp; for l, x in enumerate(A):&nbsp; &nbsp; &nbsp; &nbsp; for r in range(l+1, bisect(A, x+k, l+1)):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield l, r它使用的bisect.bisect功能来查找每个起点终点O(log n)的时间，使得整体成本O(n log n)。它甚至不需要针对 直接测试大多数值k，因为bisect找到满足不同标准的索引的末尾，并且两者之间的所有值肯定都满足它。list我没有手动构建它，而是将它变成了一个生成器函数，可以使用和解包将其转换为L和R值zip：>>> A = [3.5,5,6,12,13]&nbsp;>>> k = 1.7>>> L, R = zip(*fun(A, k))>>> print(L, R)(0, 1, 3), (1, 2, 4)你可以用lists 明确地做到这一点：def fun(A, k):&nbsp; &nbsp; L, R = [], []&nbsp; &nbsp; for l, x in enumerate(A):&nbsp; &nbsp; &nbsp; &nbsp; newr = range(l+1, bisect(A, x+k, l+1))&nbsp; &nbsp; &nbsp; &nbsp; L += [l] * len(newr)&nbsp; &nbsp; &nbsp; &nbsp; R.extend(newr)&nbsp; &nbsp; return L, R但我有点喜欢让 Python 完成大部分工作的 generator->zip->unpack 方法。无论哪种方式，理论成本O(n log n)都优于O(n * (n - 1) / 2)（大致O(n ** 2)）。