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

Question

我想找到两个数字A[i]，它们A[j]的差小于或等于K，我需要将这些数字的索引存储在数组 L (Left) R (Right) 中并返回 L & Rdef 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.7print(fun(A, k))预期输出：L[0,0,1,3,3],R[1,2,2,4,4]

Answer 1

您应该使用itertools.combinations获取所有可能的组合，然后测试它们的差异并在需要时追加。

from itertools import combinations

def fun(A, k):

    l, r = [], []

    for (x_idx, x_val), (y_idx, y_val) in combinations(enumerate(A), 2):

        if abs(x_val - y_val) <= k:

            l.append(x_idx)

            r.append(y_idx)

    return l, r

测试：

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

k = 1.7

print(fun(A, k))

# ([0, 1, 3], [1, 2, 4])

虽然这不是您的预期输出，但我觉得根据您的逻辑，您的预期输出可能会有一些错误。

Answer 2

O(n log n)在您的示例中利用排序的解决方案A（如果它没有排序，您总是可以支付O(n log n)第二次对其进行排序，尽管保留原始索引可能会使复杂性变得不值得）：

from bisect import bisect

def fun(A, k):

    # Add A.sort() if A not guaranteed to be sorted

    for l, x in enumerate(A):

        for r in range(l+1, bisect(A, x+k, l+1)):

            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] 

>>> k = 1.7

>>> L, R = zip(*fun(A, k))

>>> print(L, R)

(0, 1, 3), (1, 2, 4)

你可以用lists 明确地做到这一点：

def fun(A, k):

    L, R = [], []

    for l, x in enumerate(A):

        newr = range(l+1, bisect(A, x+k, l+1))

        L += [l] * len(newr)

        R.extend(newr)

    return L, R

但我有点喜欢让 Python 完成大部分工作的 generator->zip->unpack 方法。无论哪种方式，理论成本O(n log n)都优于O(n * (n - 1) / 2)（大致O(n ** 2)）。