6

我有两个排序的整数列表。我想分别从第一个和第二个列表中找到所有在一定距离内的整数对。

天真的方法是检查每一对，导致 O(N^2) 时间。我确信有一种方法可以在 O(N*logN) 或更短的时间内完成。

在 python 中，朴素的 O(N^2) 方法如下：

def find_items_within(list1, list2, within):
    for l1 in list1:
        for l2 in list2:
            if abs(l1 - l2) <= within:
                yield (l1, l2)

pythonic答案的加分。

应用说明

我只是想指出这个小谜题的目的。我正在搜索一个文档，并希望在另一个术语的一定距离内找到一个术语的所有出现。首先，您找到这两个术语的术语向量，然后您可以使用下面描述的算法来确定它们是否在给定距离内。

4

7 回答 7

7

没有办法做得更好，O(n^2)因为有O(n^2)对，因为within = infinity你需要让它们全部产生。

要找到这些对的数量是另一回事，可以通过找到每个元素的第一个索引来e完成within-e < arr[idx]。idx例如，可以使用二进制搜索有效地找到索引- 这将为您O(nlogn)提供找到这些对的数量的解决方案。

它也可以O(n)在线[a,b]性时间[a',b']（具有两个指针和“永不回头”的列表以获得线性时间复杂度。a>a'b>=b'

伪代码：（用于线性时间解）

numPairs <- 0
i <- 0
a <- 0
b <- 0
while (i < list1.length):
  while (a < i && list1[i] - list2[a] > within):
      a <- a+1
  while (b < list2.length && list2[b] - list1[i] < within):
      b <- b+1
  if (b > a):
      numPairs <- numPairs + (b-a)
  i <- i+1
return numPairs

（我从最初的伪代码中做了一些修复——因为第一个的目标是在单个列表中查找范围内的对数——而不是两个列表之间的匹配，对此感到抱歉）

于 2012-11-29T14:17:00.620 回答
6

此代码为 O(n*log(n)+m)，其中 m 是答案的大小。

def find_items_within(l1, l2, dist):
    l1.sort()
    l2.sort()
    b = 0
    e = 0
    ans = []
    for a in l1:
        while b < len(l2) and a - l2[b] > dist:
            b += 1
        while e < len(l2) and l2[e] - a <= dist:
            e += 1
        ans.extend([(a,x) for x in l2[b:e]])
    return ans

在最坏的情况下，可能是m = n*n，但如果答案只是所有可能对的一小部分，这会快很多。

于 2012-11-29T15:49:39.387 回答
2

这里有一些与你给出的界面相同的东西：

def find_items_within(list1, list2, within):
    i2_idx = 0
    shared = []
    for i1 in list1:
        # pop values to small
        while shared and abs(shared[0] - i1) > within: 
            shared.pop(0)
        # insert new values 
        while i2_idx < len(list2) and abs(list2[i2_idx] - i1) <= within:
            shared.append(list2[i2_idx])
            i2_idx += 1
        # return result
        for result in zip([i1] * len(shared), shared):
            yield result

for item in find_items_within([1,2,3,4,5,6], [3,4,5,6,7], 2):
    print item

不是很漂亮，但它应该可以解决问题O(N*M)，其中Nlist1 的长度和M每个 Item 的共享对列表（假设删除和附加到的元素shared平均是恒定的）。

于 2012-11-29T14:41:42.390 回答
0

您可以使用“扫描线”技术在线list2性[x - within, x + within]时间x（list1O(n)

要从list1您需要的O(m)时间枚举相应的时间间隔，其中m是时间间隔的数量，即，整体算法是O(n*m)：

from collections import namedtuple
from heapq import merge

def find_items_within(list1, list2, within):
    issorted = lambda L: all(x <= y for x, y in zip(L, L[1:]))
    assert issorted(list1) and issorted(list2) and within >= 0

    # get sorted endpoints - O(n) (due to list1, list2 are sorted)
    Event = namedtuple('Event', "endpoint x type")
    def get_events(lst, delta, type):
        return (Event(x + delta, x, type) for x in lst)
    START, POINT, END = 0, 1, 2 
    events = merge(get_events(list1, delta=-within, type=START),
                   get_events(list1, delta=within, type=END),
                   get_events(list2, delta=0, type=POINT))

    # O(n * m), m - number of points in `list1` that are 
    #               within distance from given point in `list2`
    started = set() # started intervals
    for e in events:  # O(n)
        if e.type is START: # started interval
            started.add(e.x) # O(m) is worst case (O(1) amortized)
        elif e.type is END: # ended interval
            started.remove(e.x)  # O(m) is worst case (O(1) amortized)
        else:  # found point
            assert e.type is POINT
            for x in started:  # O(m)
                yield x, e.x

允许重复值list1；x您可以为每个输入添加索引Event并使用字典index -> x而不是started集合。

于 2012-11-29T22:35:07.307 回答
0

根据列表中值的分布，您可以通过使用 binning 来加快速度：取所有值所在的范围 ( min(A+B), max(A+B))，然后将该范围划分为与D您的距离相同大小的 bin重新考虑。然后，要查找所有对，您只需要比较一个 bin 内或相邻 bin 内的值。如果您的值在许多箱之间拆分，这是避免进行 M*N 比较的简单方法。

另一种在实践中可能同样简单的技术：做一种有界线性扫描。从头开始维护列表 A 和列表 B 的索引。在每次迭代中，将索引推进到列表 A（从第一个元素开始），将此元素称为 A0。然后，将索引推进到列表 B。记住 B 的最后一个小于 A0-D 的值（这是我们要开始下一次迭代的地方）。但是，当您在 A0-D 和 A0+D 之间找到值时，请继续前进——这些是您正在寻找的对。一旦 B 中的值变得大于 A0+D，停止此迭代并开始下一个迭代 — 将一个元素进一步推进 A，并从 B < A0-D 的最后一个位置开始扫描 B。

如果平均每个元素附近有恒定数量的对，我认为这应该是 O(M+N)？

于 2012-11-29T14:35:44.700 回答
0

这似乎有效：

from itertools import takewhile
def myslice(lst,start,stop,stride=1):
    stop = len(lst) if stop is None else stop
    for i in xrange(start,stop,stride):
        yield lst[i]

def find_items_within(lst1,lst2,within):
    l2_start = 0
    for l1 in lst1:
        try:
            l2_start,l2 = next( (i,x) for i,x in enumerate(myslice(lst2,l2_start,None),l2_start) if abs(l1-x) <= within )
            yield l1,l2
            for l2 in takewhile(lambda x:(abs(l1-x) <= within), myslice(lst2,l2_start+1,None)):
                yield l1,l2
        except StopIteration:
            pass


x = range(10)
y = range(10)
print list(find_items_within(x,y,2.5))
于 2012-11-29T14:29:23.803 回答
0

此方法使用一个字典，其键是 的可能值list2，其值是 的值的列表，这些值list1在 的该值的距离内list2。

def find_items_within(list1, list2, within):
    a = {}
    for l1 in list1:
        for i in range(l1-within, l1+within+1):
            if i not in a:
                a[i] = []
            a[i].append(l1)
    for l2 in list2:
        if l2 in a:
            for l1 in a[l2]:
                yield(l1, l2)

这个复杂度有点傻。对于大小为 M 的列表 1 和大小为 N 的列表 2 和大小为 W 的范围内，它是 O(log(M*W) * (M*W + N))。在实践中，我认为它对小 W 非常有效。

奖励：这也适用于未排序的列表。

于 2012-11-29T14:43:00.783 回答