c++ - 如何找到 vector 的第二小？

Question

unsigned int i;
int min;
int num;

vector<int>sequence;

cout << "sequence: ";
for (i=0; cin.good(); ++i){
      cin >> num;
      sequence.push_back(num);
}

sequence.pop_back();

min = sequence.at(0);
for (i=0; i<sequence.size();++i){
    if (sequence.at(i)< min){
        min=sequence.at(i);
    }
}

cout << min << endl;

我想在 vector 中找到第二小的用户输入。我已经创建了一个代码来找到最小的。但我不知道如何找到第二小的。我应该在不对数字进行排序的情况下执行此操作。有人可以告诉我一个方法吗？

Answer 1

您可以在 O(n) 运行时复杂度内完成。排序将花费 O(n log n) 时间复杂度来运行。在这种情况下，您只需要两个变量即可找到第二个最小值。

#include <vector>
#include <stdio.h>
#include <iostream>
using namespace std;

int main() {
    unsigned int i;
    int min;
    int num;

    vector<int>sequence;

    cout << "sequence: ";
    for (i=0; cin.good(); ++i){
        cin >> num;
        sequence.push_back(num);
    }
    sequence.pop_back();

    int minimum = INT_MAX, secondmin = INT_MAX;

    for (i=0; i<sequence.size();++i){

       if (minimum > sequence[i]) {

           secondmin = minimum;
           minimum = sequence[i];

       }else if ( secondmin > sequence[i] ) {

           secondmin = sequence[i];

       }
    }
    cout << "answer is "<< secondmin << endl;


}

输出

sequence: 1
2
3
4
end
answer is 2