問題中提到的陣列如下：
[1,1,...,1,1,-1,-1,...,-1,-1]
如何快速找到最接近-1的1的索引？
注意：1和-1會同時存在，1和-1的個數很大。
例如，對于這樣的陣列：
[1,1,1,1,1,-1,-1,-1]
結果應該是 4。
我能想到的最快的方法是二分查找，有沒有更快的方法？
uj5u.com熱心網友回復：
使用當前的資料表示，二進制搜索是我能想到的最快的方法。當然，您可以在恒定時間內快取和重用結果，因為答案總是相同的。
另一方面，如果將陣列的表示更改為一些簡單的數字，則可以在恒定時間內找到下一個元素。由于資料始終可以映射到二進制值，因此您可以將整個陣列減少為 2 個數字。第一個磁區的長度和第二個磁區的長度。或者整個陣列的長度和磁區點。這樣，您可以在恒定時間內輕松更改兩個磁區的長度，并在恒定時間內訪問第二個磁區的下一個元素。
當然，更改陣列本身的表示是一個對數程序，因為您需要找到磁區點。
uj5u.com熱心網友回復：
通過一個簡單的資訊論論證，你不能比log(n)只使用比較快。因為有n可能的結果，你需要至少收集log(n)一些資訊來對它們進行編號。
如果您有關于值的統計分布的額外資訊，那么也許您可以利用它。但這要根據具體情況進行討論。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409381.html
標籤：
上一篇：具有相鄰差異的C 映射
下一篇：選擇N個專案，使其屬性平衡