4

给定一个数字，我必须找出给定数组中所有可能的索引对，其总和等于该数字。我目前正在使用以下算法：

def myfunc(array,num):
    dic = {}
    for x in xrange(len(array)):  # if 6 is the current key,
        if dic.has_key(num-array[x]):  #look at whether num-x is there in dic
            for y in dic[num-array[x]]: #if yes, print all key-pair values
                print (x,y),
        if dic.has_key(array[x]):  #check whether the current keyed value exists
            dic[array[x]].append(x)  #if so, append the index to the list of indexes for that keyed value
        else:
            dic[array[x]] = [x]  #else create a new array

这会及时运行O(N)吗？如果不是，那么应该怎么做才能做到这一点？O(N)而且无论如何，不​​使用任何辅助数据结构，是否有可能让它及时运行呢？

4

3 回答 3

6

这会在 O(N) 时间内运行吗？

是和不是。复杂性实际上是输出大小O(N + M)在哪里。 不幸的是，输出大小是最坏的情况，例如数组-这将导致需要生成的元素的二次数。M
O(N^2)[3,3,3,3,3,...,3]number == 6

但是 - 渐近地说 - 它不能做得比这更好，因为它在输入大小和输出大小上是线性的。

于 2012-09-23T08:00:23.477 回答
3

非常非常简单的解决方案，实际上通过使用数组引用在 O(N) 时间内运行。如果您想枚举所有输出对，那么当然（如阿米特所述）在最坏的情况下必须采用 O(N^2) 。

from collections import defaultdict
def findpairs(arr, target):
    flip = defaultdict(list)
    for i, j in enumerate(arr):
        flip[j].append(i)
    for i, j in enumerate(arr):
        if target-j in flip:
            yield i, flip[target-j]

后处理以获取所有输出值（并过滤掉(i,i)答案）：

def allpairs(arr, target):
    for i, js in findpairs(arr, target):
        for j in js:
            if i < j: yield (i, j)
于 2012-09-23T08:04:38.440 回答
1

这可能会有所帮助 -查找可被给定整数 k 整除的对所需的最佳算法

（稍作修改，我们可以看到所有可以被给定数字整除的对，不一定等于给定数字）

于 2012-09-23T09:06:02.053 回答