作者willhunting (這些年來)
看板CSSE
標題Re: [問題] 未排序的陣列，演算法相關問題
時間Sun May 9 00:59:12 2010
※ 引述《Hatred (yo)》之銘言：
: ※ 引述《mqazz1 (無法顯示)》之銘言：
: : given two unsorted arrays X and Y,
: : each contains m and n numbers, separately.
: : design an algorithm so that,
: : given a number d,
: : it could determine if there exists two integers i and j,
: : such that X[i] + Y[i] = d
: 這裡是 X[i] + Y[j] = d 吧? 不然 j 會沒有用到...
: : use less than O(m*n) running time
: : 我想請問這題大致上從哪方面下手會比較簡易
: : 謝謝
: 或許可以這樣做:
: 不妨假設 m<=n, 我們先把 d-X[1], ..., d-X[m] 算出來, 費時 O(m), 接著我們把這 m
: 個數排序成一個 array A, 費時 O(m log m). 剩下的就是檢查 Y 裡面每個元素有沒有
: 出現在 A 裡面, 若有則回答 yes, 若完全沒有則回答 no.
: 現在因為 A 已經被排序過, 所以判斷 Y 裡面任何一個元素在不在 A 裡面, 都只要
: O(log m) 時間即可 (用 binary search), 所以這步費時 O(n log m).
: 總共花的時間是
: m<=n
: O(m) + O(m log m) + O(n log m) ====== O(m log n) + O(n log m).
Hatred的這個作法不錯，不過你最後的complexity應該是O(m log m) + O(n log n)
我也有一個作法:
先排序X再排序Y: O(m log m) + O(n log n)
然後下一步比較妙
排序後的X:
x[0] x[1] x[2] ... x[m-1]
排序後的Y:
y[0] y[1] y[2] ... y[n-1]
建兩個index，x-index一開始指x[0], y-index指y[n-1]
然後查看此兩數的和
while(x-index < m && y-index < n)
{
sum = x[x-index] + y[y-index]
if sum > d
--y-index
else if sum = d
current x and y element is a pair which meets the condition
else
++x-index
}
這個方法可能不是很直覺，但其實是正確的。那個迴圈的complexity
會是O(m)+O(n)，其實正確來講是最大為m+n，兩個array頂多被整個iterate
一次而已。
所以complexity仍是O(m log m) + O(n log n)。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 74.68.114.250
1F：→ LPH66:他的後一步是 for all y in Y search y in X 05/09 01:50
2F：→ LPH66: A 05/09 01:50
3F：→ LPH66:所以後面是 O(n log m) 無誤 05/09 01:50
4F：→ willhunting:對 我打錯了 只有第一個是O(m log m) 05/09 03:23