我正在学习数据结构考试,我试图解决这个问题:
给定一个n个数的数组和一个Z数,在O(n)平均时间内找到x,y(如x+y=Z )。
我的建议是将数组的内容移到哈希表中,并使用打开寻址执行以下操作:
对于每个数字,Ai在哈希表中搜索Z-Ai (每个操作平均为O(1))。最坏的情况是,执行n次搜索,O(1)次平均时间,即平均O(n)次。
我的分析正确吗?
发布于 2013-07-03 06:49:57
假设您是第二次遍历所有数组,是的,即O(n) * O(1) (而不是前面我说过的O(n)+O(1) )(用于平均时间的哈希查找),所以您讨论的是O(n)复杂度的算法。
https://stackoverflow.com/questions/17441323
复制相似问题