100分求救，算法的问题__nlgn_查找_step_lgn_binary_

当前位置: 技术问答>java相关

100分求救，算法的问题

来源: 互联网发布时间：2015-09-23

本文导语: 给定一个整数集合s，和一个整数n，设计一个时间复杂度为nlgn的算法找出集合s中两数之和为n的数。 | 你想想把集合s的元素先进行一次堆排序变成一个有序表，（heap sort O(n)~nlgn) 然后从第一个元素开...

给定一个整数集合s，和一个整数n，设计一个时间复杂度为nlgn的算法
找出集合s中两数之和为n的数。

你想想
把集合s的元素先进行一次堆排序变成一个有序表，
（heap sort O(n)~nlgn)
然后从第一个元素开始，比如5,那么你应该查找n-5,
然后对这个有序表用二分查找n-5(或者插值法，分块法都行）
（binary search O(n)~ lgn)
如果找到了，就把n和n-5都从表内删除,放在结果集里
如果没找到，什么也不做
查找完这个元素，在查找下一个元素
最坏情况下，一共要查找n次
n个二分查找 O(n)~ n*lgn
最终，O(n)~ nlgn

这些算法，书上都有，不用我给你写代码了吧？

step 1:先排序
    将集合S用数组存储。设s有m个数
    若m较大，则用堆排序,O(mlogm)；
    否则，用快速排序，平均时间kmlnm

step 2:找两者之和为n的数  (设无相同的数）
    i=0;
    j=m-1;
    while(i