什麼是查找排序範圍內元素數量的最快方法？

鑑於排序列表
1, 3, 5, 6, 9....
是否有一個快速的算法，而不是O(n)計算給定範圍內[a, b]元素的數量，假設所有的數字都是整數？什麼是查找排序範圍內元素數量的最快方法？

來源

2013-02-07 Chan

哪種語言？ – sgarizvi

我很好用C/C++，Java或C＃。會把語言標籤。提前致謝。 – Chan

'std :: lower_bound'和'std :: upper_bound'？給你比你要求的更多... – Mehrdad

這是一個O（log n）算法：使用binary search搜索兩個端點，那麼範圍內的元素數量基本上就是指數的差異。

爲了得到一個需要區分其中該範圍的端點是陣列中與否的情況下的具體數量。

來源

2013-02-07 06:40:09 Henry

你需要走差異化加一？我認爲這是關閉的。 – templatetypedef

@templatetypedef可能是的，有幾種情況取決於端點是否實際存在於數組中。 – Henry

也假定數據結構是可索引的。例如，如果排序的數據結構是鏈接列表或樹，則不存在索引。 OP說*排序列表* ...在這種情況下，您必須從a遍歷到b。這是（結果 - [a，b]中元素的數量），所以你的總數是log n + log n +（結果 - [a，b]中元素的數量） – thang

由於列表進行排序，你可以找到一個值的位置（或者，如果該值不在列表中，它應該被插入）在O（日誌（n））的時間。您只需在兩端執行此操作，然後減去以獲取範圍內元素的數量。元素是否是整數都沒有區別;該列表只需要進行排序。

你確實需要小心，如果該元素是不是唯一的;在這種情況下，在找到命中後，您可能需要對重複元素序列的末尾進行線性掃描。

來源

2013-02-07 06:41:16

lower_bound和upper_bound上有序容器操作。

首先找到該範圍中的較低的值，然後從那裏搜索到最後的上限值。函數的實現可能使用二進制搜索：

#include <algorithm> 
#include <list> 
#include <iterator> 

int main() { 
    using std::list; 
    using std::upper_bound; 
    using std::lower_bound; 
    using std::distance; 

    list<int> numbers = {1, 3, 5, 6, 9}; 
    int a = 3; 
    int b = 6; 

    auto lower = lower_bound(numbers.begin(), numbers.end(), 
          a); 
    auto upper = upper_bound(lower, numbers.end(), 
          b); 

    int count = distance(lower, upper); 

    return 0; 
}

來源

2013-02-07 08:14:56

什麼是查找排序範圍內元素數量的最快方法？

回答

相關問題