gpt4 book ai didi

python - 更好的算法(比使用字典)来枚举具有给定总和的对。

转载 作者:太空狗 更新时间:2023-10-30 01:59:41 24 4
gpt4 key购买 nike

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

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) 时间内运行?

最佳答案

Will this run in O(N) time?

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

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

关于python - 更好的算法(比使用字典)来枚举具有给定总和的对。,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12550645/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com