這是<<算法導(dǎo)論>>中的一題,exercise 2.3-7.
可以這么做:
1) 首先將序列排序,去掉重復(fù)的元素.
2) 其次生成一個(gè)序列, 該序列中每個(gè)元素都是X-原序列中的值, 同樣的,去重.
3) 對這兩個(gè)已經(jīng)排序好的序列進(jìn)行合并操作.
4) 如果有兩個(gè)元素之和為X, 那么在合并的時(shí)候必然是相鄰的元素.
比如序列 1, 3, 5, 8, X=8, 生成的新序列排序之后就是0, 3, 5, 7.在合并操作時(shí)出現(xiàn)兩個(gè)相鄰的3,因此該序列中存在3和5之和為8.
我想的另一種做法:
遍歷序列, 每次遍歷時(shí)將X-序列元素的差放入到另一個(gè)新的序列中的合適位置去, 使這個(gè)新的序列一直都是有序的.同樣的, 每次遍歷的時(shí)候都在這個(gè)新的序列中搜索是否存在當(dāng)前元素, 由于是有序的, 所以可以采用二分查找的方法.
比如對于序列5,1,8,3, X=8.
首先遍歷的元素是5, 此時(shí)新的序列是空的,將8-5=3放入到新的序列中.
其次遍歷的元素是1, 此時(shí)新的序列只有元素3, 將8-1=7放入到新的序列中, 形成3,7的有序序列.
再次遍歷的元素是8, 此時(shí)新的序列為3,7, 將8-8=0放入到新的序列中, 形成0,3,7的有序序列.
最后遍歷的元素是3, 此時(shí)新的序列是0,3,7, 查找3成功, 退出.
不過, 很顯然, 第二種方法并不能達(dá)到題目要求的nlg(n)的要求.但是, 它的優(yōu)點(diǎn)在于, 不一定非得遍歷完序列的所有元素就可以找到答案.
另外,這個(gè)題目給我的另一個(gè)啟示就是,在很多問題中, 排序和搜索算法絕對是最基礎(chǔ)的組成部分,你可能不會直接使用到它們, 但是會間接的使用或者借鑒到其中的想法幫助你解決問題.所以, 不管是效率比較低的插入算法也好, 還是快速排序也好, 都要進(jìn)行研究, 并且掌握其中蘊(yùn)藏的思想.