C-快速寻找满足条件的两个数(和为某个数)

WordPress 开发 WordPress 开发 主题:1098 回复:2322

C-快速寻找满足条件的两个数(和为某个数)

甜柠檬 发布于 2017-07-17 字数 472 浏览 982 回复 6

编程之美2.12讲了这么一个问题:
题目:快速找出一个数组中的两个数,让这两个数之和等于一个给定的值。
比如5 6 1 4 7 9 8求出sum=10的一组数,假设存在这样的数。书上给出了O(nlogn)的实现,现在请问一下,有没有更好的算法时间复杂度达到O(n)?我想是不是可以这样子定义一个数组a[5]=1,a[6]=1,a[4]=1,a[7]=1,a[9]=1,a[8]=1,然后其他的当然a[i]=0啦,然后寻找和为10的,比如a[6]看看if(a[4] == 1)...。这种方法是否可行?还有如果是浮点数怎么办?如果数很大怎么办?有没有可能做到O(n)?

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(6

瑾兮 2017-09-20 6 楼

对于整数,我觉得用hash和位图都不错,位图的话可能就取决于你的最大那个数了,如果你最大那个数比较小的话,用位图还是蛮省空间的。

对于浮点型的话,比较好的方法还是先排序,然后用两个下标,一前一后进行夹逼找呢~

夜无邪 2017-08-24 5 楼

这个一般涉及到排序和比较的方法,效率就不可能为O(n),上面也说了,如果是整数可以用hash。

夜无邪 2017-08-17 4 楼

这个问题,正常来说nlogn就是最小的了,因为你要找的是两个数,那么第一个最少就是o(n),然后查找的话,logn是最小的了吧,然后不就是nlogn么,这里首先第一个不可能变少,因为你每个都要遍历过来,然后查找的话,O(1)的大约就是hash了,不过明显hash要先遍历然后建立hash表的~~所以要建立hash表的话也可以降低到O(n),也可能有其他方法吧~

归属感 2017-08-10 3 楼

其实你的问题就是数组排序问题,所以根本就不可能达到你说的O(N)时间复杂度。最多就是快速排序的速度了。之所以说是数组排序问题是因为你的问题与数组排序问题只是比较条件换了,排序时比较大小,而你的则是比较两个数是否和为零。

当然如果你的这组数据要重复多次使用,也可以建议一个hash,然后进行查询。

甜柠檬 2017-08-08 2 楼

提问者构思的排序算法是可以的,它还有个名字,叫桶排序。
当每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
但还有查找,
sum为偶数时最坏情况,O((sum-2)/2)),
sum为奇数时最坏情况,O((sum-1)/2)),
当然了,最好情况是O(1)。
使用桶排序做这道题,最好情况是O(N),但平均时间复杂度要看sum的值。

http://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F

偏爱自由 2017-07-20 1 楼

整数的话可以用hash来获得O(1)的查找效率。
首先遍历一遍数组,建立hash表O(N)。
然后再次遍历数组,对每一个数字a进行查找sum-a只需O(1),
所以总的效率为:O(N)+O(N)*O(1)=O(N).