查找範圍內的最大和第二大元素

Question

如何在不刪除最大元素並再次搜索的情況下找到上述內容？有沒有更有效的方法來做到這一點？這些元素是否重複並不重要。

Answer 1

for (e: all elements) { 
if (e > largest) { 
    second = largest; 
    largest = e; 
} else if (e > second) { 
    second = e; 
} 
} 

你既可以初始化largest和second到合適的下界，或在列表中的前兩個項目（檢查哪一個更大，並且不要忘記檢查，如果列表中有至少兩個項目）

Answer 2

從n..m創建一個子列表，排序，上去下來。然後抓住前兩個元素。從原始列表中刪除這些元素。

Answer 3

使用partial_sort？

std::partial_sort(aTest.begin(), aTest.begin() + 2, aTest.end(), Functor); 

一個例子：

std::vector<int> aTest; 

    aTest.push_back(3); 
    aTest.push_back(2); 
    aTest.push_back(4); 
    aTest.push_back(1); 


    std::partial_sort(aTest.begin(), aTest.begin()+2,aTest.end(), std::greater<int>()); 

    int Max = aTest[0]; 
int SecMax = aTest[1]; 

Answer 4

讓我們假設你的意思是在列表中找到最大的兩個獨特的價值觀。

如果列表已經排序，那麼就看看倒數第二個元素（或者說，從最終尋找的倒數第二個值重複）。

如果列表未排序，那就不必對它進行排序。排序最好是O（n lg n）。簡單的線性迭代是O（n），所以剛過跟蹤元素循環：

v::value_type second_best = 0, best = 0; 
for(v::const_iterator i=v.begin(); i!=v.end(); ++i) 
    if(*i > best) { 
    second_best = best; 
    best = *i; 
    } else if(*i > second_best) { 
    second_best = *i; 
    } 

當然還有其他的標準，而這些可以全部投入到循環內的測試。但是，如果您的意思是應該找到兩個都具有相同最大值的元素，則必須考慮如果三個或更多元素都具有最大值，或者如果兩個或更多個元素具有第二大值，會發生什麼情況。

Answer 5

您可以掃描一遍列表，並保存第一和第二值，具有O（n）的效率，同時排序是O（n log n）的。

編輯：
我認爲這部分的排序是O（n日誌k）的

Answer 6

答案取決於如果你只想值，或也可以在值指向迭代器。

@ will回答的小修改。

v::value_type second_best = 0, best = 0; 
for(v::const_iterator i=v.begin(); i!=v.end(); ++i) 
{ 
    if(*i > best) 
    { 
    second_best = best; 
    best = *i; 
    } 
    else if (*i > second_best) 
    { 
    second_best = *i; 
    } 
} 

Answer 7

nth_element（開始，開始+ N，端，比較）放置，這將是第n個元素（其中，「第一」是「第0」）如果[範圍開始，結束）的位置進行分選開始+並確保[begin，begin + n）中的所有內容都出現在排序列表中的第n個元素之前。所以，你想要的代碼是：

nth_element(container.begin(), 
      container.begin()+1, 
      container.end(), 
      appropriateCompare); 

這會在你的情況下工作得很好，因爲你只想找兩個最大。假設你appropriateCompare從最大的事情進行排序到最小，與是在位置1和最大的第二大元素將在位置0

Answer 8

最優算法不應該需要超過1.5 * N - 2的比較。 （一旦我們確定它是O（n），N？2 * N比較前面的係數是不是最優的）。

因此，首先確定每對中的「贏家」和「輸家」 - 即0.5 * N的比較。

然後通過比較獲勝者來確定最大的元素 - 這是另一個0.5 * N - 1的比較。

然後通過比較其中最大元素來自其他所有對的獲勝者的對的失敗者來確定第二大元素 - 另一個0.5 * N-1比較。

總比較= 1.5 N - 2

Answer 9

未經測試，但有趣：

template <typename T, int n> 
class top_n_functor : public unary_function<T, void> 
{ 

    void operator() (const T& x) { 
    auto f = lower_bound(values_.begin(), values_.end(), x); 

    if(values_.size() < n) { 
     values_.insert(f, x); 
     return; 
    } 

    if(values_.begin() == f) 
      return; 

    auto removed = values_.begin(); 
    values_.splice(removed, values_, removed+1, f); 

    *removed = x; 
    } 

    std::list<T> values() { 
    return values_; 
    } 
private: 
    std::list<T> values_; 
}; 

int main() 
{ 
    int A[] = {1, 4, 2, 8, 5, 7}; 
    const int N = sizeof(A)/sizeof(int); 

    auto vals = for_each(A, A + N, top_n_functor<int,2>()).values(); 

    cout << "The top is " << vals.front() 
     << " with second place being " << *(vals.begin()+1) << endl; 
} 

Answer 10

如果最大是第一要素，搜索第二大[最大+ 1，結束）。否則搜索[開始，最大）和[最大+ 1，結束），並取兩者中的最大值。當然，這有O（2n），所以它不是最優的。

如果您有隨機訪問迭代器，你可以做的是快速排序並和使用不斷優雅遞歸：

template< typename T > 
std::pair<T,T> find_two_largest(const std::pair<T,T>& lhs, const std::pair<T,T>& rhs) 
{ 
    // implementation finding the two largest of the four values left as an exercise :) 
} 

template< typename RAIter > 
std::pair< typename std::iterator_traits<RAIter>::value_type 
     , typename std::iterator_traits<RAIter>::value_type > 
find_two_largest(RAIter begin, RAIter end) 
{ 
    const ptr_diff_t diff = end-begin; 
    if(diff < 2) 
    return std::make_pair(*begin, *begin); 
    if(diff < 3) 
    return std::make_pair(*begin, *begin+1); 
    const RAIter middle = begin + (diff)/2; 
    typedef std::pair< typename std::iterator_traits<RAIter>::value_type 
        , typename std::iterator_traits<RAIter>::value_type > 
    result_t; 
    const result_t left = find_two_largest(begin,middle); 
    const result_t right = find_two_largest(middle,end); 

    return find_two_largest(left,right); 
} 

這有O（n）和不應超過NomeN's implementation使更多的比較。

Answer 11

前k通常是有點大於n更好（日誌K）

template <class t,class ordering> 
class TopK { 
public: 
    typedef std::multiset<t,ordering,special_allocator> BEST_t; 
    BEST_t best; 
    const size_t K; 
    TopK(const size_t k) 
     : K(k){ 
    } 
    const BEST_t& insert(const t& item){ 
     if(best.size()<k){ 
      best.insert(item); 
      return best; 
     } 
     //k items in multiset now 
     //and here is why its better - because if the distribution is random then 
     //this and comparison above are usually the comparisons that is done; 
     if(compare(*best.begin(),item){//item better than worst 
      erase(begin());//the worst 
      best.insert(item); //log k-1 average as only k-1 items in best 
     } 
     return best; 
    } 
    template <class it> 
    const BEST_t& insert(it i,const it last){ 
     for(;i!=last;++i){ 
      insert(*i);  
     } 
     return best; 
    } 
    }; 

當然的special_allocator可以在本質上只是ķ多集value_types的陣列，並且（那些節點的列表，其典型地具有無因爲其他k正在multiset中使用，直到它的時間來放入一個新的，然後我們擦除然後立即重新使用它。好或者在std :: multiset和緩存中有內存alloc/free它是一個非常微小的工作，它可以在不違反STL分配器規則的情況下使其處於靜態狀態。但是對於固定的k<<n，我會選擇GUESS（2n + delta * n），其中delta是小的 - 我的DEK ACP vol3 S & S被打包掉了，對delta的估計是我想做的更多工作。

平均最差的是我會猜測n（log（k-1）+ 2）時，以相反的順序和所有不同。

最好是2n + k（log k）k最好是第一個