作者Hatred (yo)
看板CSSE
標題Re: [問題] 未排序的陣列，演算法相關問題
時間Sat May 8 12:23:29 2010
※ 引述《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).
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.124.99.236