这是<<算法导论>>中的一题,exercise 2.3-7.
可以这么做:
1) 首先将序列排序,去掉重复的元素.
2) 其次生成一个序列, 该序列中每个元素都是X-原序列中的值, 同样的,去重.
3) 对这两个已经排序好的序列进行合并操作.
4) 如果有两个元素之和为X, 那么在合并的时候必然是相邻的元素.
比如序列 1, 3, 5, 8, X=8, 生成的新序列排序之后就是0, 3, 5, 7.在合并操作时出现两个相邻的3,因此该序列中存在3和5之和为8.
我想的另一种做法:
遍历序列, 每次遍历时将X-序列元素的差放入到另一个新的序列中的合适位置去, 使这个新的序列一直都是有序的.同样的, 每次遍历的时候都在这个新的序列中搜索是否存在当前元素, 由于是有序的, 所以可以采用二分查找的方法.
比如对于序列5,1,8,3, X=8.
首先遍历的元素是5, 此时新的序列是空的,将8-5=3放入到新的序列中.
其次遍历的元素是1, 此时新的序列只有元素3, 将8-1=7放入到新的序列中, 形成3,7的有序序列.
再次遍历的元素是8, 此时新的序列为3,7, 将8-8=0放入到新的序列中, 形成0,3,7的有序序列.
最后遍历的元素是3, 此时新的序列是0,3,7, 查找3成功, 退出.
不过, 很显然, 第二种方法并不能达到题目要求的nlg(n)的要求.但是, 它的优点在于, 不一定非得遍历完序列的所有元素就可以找到答案.
另外,这个题目给我的另一个启示就是,在很多问题中, 排序和搜索算法绝对是最基础的组成部分,你可能不会直接使用到它们, 但是会间接的使用或者借鉴到其中的想法帮助你解决问题.所以, 不管是效率比较低的插入算法也好, 还是快速排序也好, 都要进行研究, 并且掌握其中蕴藏的思想.