查找連續元素相差1的數組中的元素

有一個數組，任何兩個結果元素之間的距離爲1（+ 1/-1）。你將如何找到它的一個元素。它可以在小於O（n）時間內完成查找連續元素相差1的數組中的元素

2011-09-04 shreyasva

那你試試？ – PengOne

只需從第一個位置開始;現在考慮搜索的數字m ;之間的差異，如果array[0] == m那麼我們完成;否則我們必須跳abs(array[0] - m)職位;現在重複這個直到數組結束。

但是，我們不能比爲O（n）做的更好最壞的情況下，只考慮這種情況下，我們要找出11：

10 9 8 9 8 9 10 9 8 9 8 9 10 9 8 9 8 9 10 9 8 9 8 9

2011-09-04 17:56:36 Simone

「否則」和「職位」之間的部分不具有語法意義。你可以嘗試修復嗎？ – Svante

這裏有一個簡單的想法，應該可以幫助您思考問題。

如果您正在尋找x和abs(x-array[0]) == k，那麼你不妨跳轉到array[k]。

想想這個，你會得到你的算法。

現在，請考慮此算法的最壞情況。你能做到這一點，所以大多數條目必須檢查？（提示：是）

2011-09-04 17:41:55 PengOne

回答