查找范围中的最大和第二大元素

Question

如何在不删除最大元素并再次搜索的情况下找到上述内容？有没有更有效的方法来做到这一点？这些元素是否重复并不重要。

Answer 1

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

您可以将largest和second初始化为适当的下限，或者将列表中的前两项初始化（检查哪一项更大，并且不要忘记检查列表是否至少有两个项）

Answer 2

使用 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 3

nth_element（begin，begin + n，end，Compare）如果范围 [begin，则将元素置于第n个（其中“first”是“0th”）） <）> 在 begin + n 的位置排序，并确保 [begin，begin + n] 中的所有内容都出现在排序列表中的第n个元素之前。所以你想要的代码是：

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

这对你的情况很有用，因为你只是寻找最大的两个。假设您的适当比较从最大到最小排序，第二个元素位于第1位，最大元素位于第0位。

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

最佳算法不需要超过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 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

从n..m创建一个子列表，按降序排序。然后抓住前两个元素。从原始列表中删除这些元素。

Answer 8

您可以一次扫描列表并保存第一个和第二个值，这些值具有O（n）效率，而排序为O（n log n）。

编辑：结果 我认为部分排序是O（n log k）

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，结束]中搜索第二个元素。否则搜索[begin，largest]和[maximum + 1，end]并取两者中的最大值。当然，这有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的实施。

Answer 11

top k通常比n（log 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 本质上可以只是一个k multiset value_types的数组和那些节点的列表（它们通常没有任何内容，因为其他k在multiset中使用，直到它是时候把一个新的，然后我们擦除，然后立即重用它。很高兴有这个或者在std :: multiset中的内存alloc / free和缓存行废话杀死你。它是一个（非常）微小的工作在不违反STL分配器规则的情况下给它静态。

不如精确2的专用算法好，但对于固定 k＆lt;＆lt; n ，我会GUESS（2n + delta * n），其中delta很小 - 我的DEK ACP vol3 S＆amp; S被打包了，对delta的估计是我想要做的更多工作。

平均最差的是我猜n（log（k-1）+ 2）当它们处于相反的顺序而且都是不同的。

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