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

Question

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

Answer 1

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

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

你可以初始化largest和second适当的下限,或者列表中的前两项(检查哪一个更大,不要忘记检查列表是否至少有两个项目)

Answer 3

nth_element(begin, begin+n,end,Compare)如果范围[begin, end)在位置排序begin+n并确保所有内容[begin,begin+n)都出现在排序列表中的第n个元素之前,则将元素放置为第n个(其中"first"为"0th").所以你想要的代码是:

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

这将适用于您的情况,因为您只寻找两个最大的.假设您的适当比较从最大到最小排序,第二个最大元素位于第1位,最大元素位于第0位.