我目前正在參加有競爭力的課程。我遇到了一個函數調用問題,其中一個任務要求我在deque內查找值。不幸的是,我目前的實現時間複雜度爲O(N)
,而且速度太慢。C++ STL Deque search:太慢?
我的代碼,例如:
deque<int>::iterator find(int ref) {
for (deque<int>::iterator it = d.begin(); it != d.end(); ++it) {
if (*it == ref) return it;
}
return d.begin();
}
四處詢問之後,我想通了,我需要數時間複雜度O(log N)
爲了避免超出(TLE)錯誤的時間限制。請幫忙,謝謝!
你似乎使用了錯誤的數據結構。對於O(log N)查找,您需要一個已排序的數據結構。 –
正如@SanderDeDycker所說,考慮存儲您的ints排序,然後您可以使用std :: binary_search具有對數複雜性。 – Oleg
你被允許自己構建雙端隊列嗎?你能否對這個deque的內容做出任何假設?如果不是,那麼沒有比線性算法更快的。順便說一句,如果目標沒有找到就返回開始迭代器就是愚蠢的。你怎麼知道第一個元素是匹配還是不匹配? – user2079303