0

我正在尝试在具有特定差异的数字列表中查找对数。说，用清单

1 2 3 4 5

和差异目标'2'，我想打印数字'3'，因为这个序列中有3对差异为'2'。但是，我的代码非常慢 - 它重复计算所有对，所以我最终需要将我的解决方案除以 2 才能得到答案。有没有办法在不重复计算的情况下完成同样的任务？我很欣赏你可能有的任何见解。谢谢！代码打印在下面

    import sys


    def main():
        solutions=0
        pairs=[]
        for i in xrange(len(numbers)):
            for j in xrange(len(numbers)):
                if i!=j:
                    pairs.append([numbers[i], numbers[j]])

        for pair in pairs:
            if abs(pair[0]-pair[1])==k:
                solutions+=1
            else:
                continue
        return solutions/2



    if __name__ == '__main__':
        lines=sys.stdin.readlines()
        n,k=map(int, lines[0].strip().split())
        numbers=map(int, lines[1].strip().split())
        print main()
4

3 回答 3

3

对于 中的每个元素i，a您要检查是否i-diff也在 中a。对于~O(1) 成员资格测试，我们可以使用一个集合。因此：

>>> a = [1,2,3,4,5]
>>> diff = 2
>>> a_set = set(a)
>>> sum(i-diff in a_set for i in a_set)
3

这是O（len（a））。

[请注意，我使用了一个事实i-diff in a_set，即 a bool，计算结果1为int。这相当于sum(1 for i in a_set if i-diff in a_set)。]

更新：在我看来，我假设这些数字是唯一的。如果不是，那没关系，我们可以只使用 acollections.Counter来保留多重性信息。

于 2013-01-12T05:56:49.083 回答
0

如果对数组进行排序，则只需遍历数组即可找到所有对，而不是进行 O(n^2) 搜索。重复计算的原因是您使用abs了所以它不仅找到（1,3）而且找到（3,1）。

于 2013-01-12T05:50:55.240 回答
0

首先对数组进行排序，然后对num列表中需要查找的每个数字（）进行排序num-2。我想最快的方法是通过binary search.

所以，通过二分搜索，你会得到一个O(n log(n))解决方案。

于 2013-01-12T05:52:24.977 回答