寻找第二个最小值

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

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

Answer 2

您可以使用STL算法nth_element，复杂度为O（n）：

#include <iostream>
#include <algorithm>

int main(int argc, char** argv) {
    int a[5]={7,5,45,89,12};
    std::nth_element(a, a + 1, a + 5);
    std::cout << "second smallest value is: " << a[1];
    return 0;
}

如果要保持数组a不变，可以partial_sort_copy改用。

int a[5]={7,5,45,89,12}, b[2];
std::partial_sort_copy(a, a + 5, b, b + 2);
std::cout << "second smallest value is: " << b[1];

在这种情况下，复杂度也是O（n）。