面试题求助!!在一个集合里面找出两个元素之和为一定数值的算法!
已知有一个包含n个数的集合S以及一个常数c,设计一个时间复杂度为O(nlgn)的算法,以确定在集合S中是否存在两个数,它们的和为常数c.
我只想出用两次遍历...也就是复杂度为O(n2),请教一下如何可以获得O(nlgn)的算法?
[解决办法]
排序(onlogn);
对其中的每个元素ai,二分查找(c-ai),(onlogn)
[解决办法]
http://topic.csdn.net/u/20080314/21/7fff8e74-ed62-4d34-90c9-8d4e05bc52a4.html
[解决办法]
遍历集合S 对每个数n 作a=c-n 将a放入数组ss中 放的时候用二分法插入 保证SS的有序性 在遍历S的同时 在SS中用二分法查找n是否存在
