c++ - 找到第二个最小值

Question

我想在数组列表中找到第二个最小值。这是我的代码。有更好的方法吗？

int main(){
    int a[5]={7,5,45,89,12};
    int smallest=a[0];
    int index;
    for(int i=0;i<5;i++){
        if(a[i]<smallest){
            smallest=a[i];
            index=i;
        }
    }

    smallest=a[0];
    for(int i=0;i<5;i++){
        cout<<i;
        if((a[i]<smallest )&& (i!=index)){
            smallest=a[i];
        }
    }
    cout<<"second smallest value is: "<<smallest;  

此代码在 O(n) 时间内运行？对于第一个循环，它需要 n 个步骤，对于另一个 for 循环，它也需要 n 个步骤。因此总共需要 O(n) 时间复杂度。
这是对的吗？如果我错了，有人可以纠正我吗

Answer 1

是的，是 O(n)，但实际上没有必要遍历列表两次。

您可以通过存储最小值和次小值来完成一次。

例如，考虑以下伪代码:

smallest = a[0]
second = a[1]
if second < smallest:
    swap second with smallest
for each index 2 thru a.size - 1 inclusive:
    if a[index] < smallest:
        second = smallest
        smallest = a[index]
    else:
        if a[index] < second:
            second = a[index]

这也是 O(n) 但它只遍历列表一次，而不是两次。最后，second 保持第二高的值。

请记住，列表 {1, 1, 2} 中第二高的值是 1。如果您想以不同的方式处理重复项，只需稍作修改即可。

---

在 Python 中用示例作为概念证明来实现它，显示结果:

a = [1,45,2,96,4,35]
smallest = a[0]
second = a[1]
if second < smallest:
    smallest, second = second, smallest
for index in range (2, len(a)):
    if a[index] < smallest:
        second = smallest
        smallest = a[index]
    else:
        if a[index] < second:
            second = a[index]
print smallest
print second

它的输出是:

1
2

作为最小和第二小的数字。