尋找固定的和----2013年2月26日

問題描述:有兩個數組x[]與y[]，各有m與n個元素，而且各個元素沒有依順序排列；d是一個已知的值。請寫一個程式，看看在x[]與y[]中有沒有滿足x[i]+y[j]=d的元素。例如，若x[]為3,7,2,4,y[]為1,5,2,3,d為9；那麼x[1]+y[2]與x[3]+y[1]都合乎條件，也即都是9。

     思路:x[i]+y[j]=d。那麼x[i]=d-y[j]了。将x[]數組按從小到大的順序排序好，再用二分查找法在x[]中查找d-y[j]。這是比較簡單的方法。但是這種方法比較不容易想到，因為這個問題給出的隐性思路是在x[]與y[]這兩個數組中查找，而這種二分查找法是将2個查找轉化成了一個查找。

     代碼比較簡單，用一種比較高效的排序算法進行排序，再用二分查找法就可以了。代碼略。

本文轉自NeilHappy 51CTO部落格，原文連結：http://blog.51cto.com/neilhappy/1140323，如需轉載請自行聯系原作者