时间戳

首页 > 解决方案 > 如何找到第二小的向量？

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

问题描述

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;

我想在向量中找到第二小的用户输入。我创建了一个代码来找到最小的。但我不知道如何找到第二小的。我应该这样做而不对数字进行排序。有人可以告诉我一个方法吗？

标签： c++

解决方案

您可以在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

推荐阅读