7

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

4

12 回答 12

22

使用部分排序？

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];
于 2009-09-11T19:12:02.760 回答
22 
for (e: all elements) {
 if (e > largest) {
   second = largest;
   largest = e;
 } else if (e > second) {
   second = e;
 }
}

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

于 2009-09-11T19:13:57.623 回答
7

nth_element(begin, begin+n,end,Compare)[begin, end)如果范围按位置排序，则放置第 n 个元素（其中“第一个”是“第 0 个”），begin+n并确保所有 from[begin,begin+n)将出现在排序列表中的第 n 个元素之前。所以你想要的代码是：

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

这在您的情况下会很好用，因为您只在寻找最大的两个。假设您的适当Compare 从最大到最小对事物进行排序，则位于位置 1 的第二大元素将位于位置 0。

于 2009-09-11T19:27:02.213 回答
2

假设您的意思是在列表中找到两个最大的唯一值。

如果列表已经排序，则只需查看倒数第二个元素（或者更确切地说，从末尾迭代以查找倒数第二个值）。

如果列表未排序，则不必费心对其进行排序。排序最多为 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;
   }

当然还有其他标准，这些都可以放入循环内的测试中。但是，如果您的意思是应该找到两个具有相同最大值的元素，您必须考虑如果三个或更多元素都具有这个最大值，或者如果两个或更多元素具有第二大值，会发生什么情况。

于 2009-09-11T19:13:01.403 回答
2

最佳算法不需要超过 1.5 * N - 2 次比较。（一旦我们确定它是 O(n)，N 前面的系数是多少？2 * N 比较不是最优的）。

因此，首先确定每对中的“赢家”和“输家”——即 0.5 * N 次比较。

然后通过比较获胜者来确定最大的元素——这又是 0.5 * N - 1 次比较。

然后通过将最大元素来自的对的失败者与所有其他对的获胜者进行比较来确定第二大元素 - 再进行 0.5 * N - 1 次比较。

总比较 = 1.5 N - 2。

于 2009-09-11T19:39:22.057 回答
1

答案取决于您是只想要这些值，还是需要指向这些值的迭代器。

@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;
   }
}
于 2009-09-11T19:25:58.017 回答
0

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

于 2009-09-11T19:11:26.117 回答
0

您可以一次扫描列表并保存第一个和第二个值，其效率为 O(n)，而排序为 O(n log n)。

编辑：
我认为部分排序是 O(n log k)

于 2009-09-11T19:18:39.123 回答
0

未经测试但很有趣：

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;
}
于 2009-09-11T19:40:37.793 回答
0

如果最大的是第一个元素，则在 [largest+1,end) 中搜索第二大的元素。否则在 [begin,largest) 和 [largest+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 的 implementation进行更多的比较。

于 2009-09-11T20:01:48.757 回答
0

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 多集 value_types 的数组和这些节点的列表（通常没有任何内容，因为其他 k 正在多集中使用，直到需要放入一个新的并且我们擦除和然后立即重用它。很高兴拥有这个，否则 std::multiset 中的内存分配/释放和缓存行废话会杀死你。在不违反 STL 分配器规则的情况下赋予它静态状态是一项（非常）微小的工作。

不如 2 的专用算法好，但对于固定的k<<n，我会 GUESS (2n+delta*n) 其中 delta 很小 - 我的 DEK ACP vol3 S&S 被打包了，对 delta 的估计是我想要的更多工作去做。

平均最差的是我猜 n(log(k-1) + 2) 当顺序相反并且完全不同时。

best is 2n + k(log k) for the k best is the first

于 2009-09-25T20:50:02.780 回答
0

我认为您可以实现自定义数组并重载元素的索引获取/设置方法。然后在每次设置调用时，将新值与结果的两个字段进行比较。虽然这会使 setter 变慢，但它受益于缓存甚至寄存器。然后它没有操作来获得结果。如果每次查找最大值仅填充一次数组，这必须更快。但是如果经常修改数组，那么它会变慢。

如果在向量化循环中使用数组，那么实现起来会变得更加困难，因为您必须在 setter 中使用 avx/sse 优化的 max 方法。

于 2022-03-01T13:22:17.257 回答