找到第二个最小值

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)。

Answer 3

你可以用一个循环来处理它：

int smallest = max
int second = max;

for( int i = 0; i < len; ++i){
    if( a[i] <= smallest){ 
        second = smallest;
        smallest = a[i];
    } else if( a[i] < second){
        second = a[i];
    }
}

max

 应该是尽可能高的值。 

len

数组的长度。

这也将在 O(n) 时间内运行。

Answer 4

您可以在循环的一次迭代中完成此操作：

int main(){
    int a[5]={7,5,45,89,12};
    int smallest = a[0]; 
    int smallest2 = a[0];
    for(int i=1;i<5;i++){
        if(a[i]  < smallest2){
            if(a[i]  < smallest){
              smallest=a[i];
            }
            else {
                smallest2 = a[i];
            }
        }
    }
    cout<<smallest << endl;
    cout<<smallest2 << endl;
    return 0;
}

Answer 5

解决此问题的另一个好方法是使用 MINHEAP。

算法：

1. 从数组中构建一棵最小堆树。复杂度 = O(n)

2. 现在提取根节点（最小）并再次对数组进行最小堆化。复杂度 = O(logn)

3. 现在提取根上第二小的元素。复杂度 = O(logn).

4. 要找到第 k 个最小元素，复杂度变为 O(n) + O(klogn)。

这里因为你需要第二小的元素，所以复杂度是 O(n) + O(2logn)

Answer 6

可以对数组进行升序排序，得到第二个元素：

#include <iostream>
#include <algorithm>

int main(int argc, char **argv)
{
    int a[5] = {7, 5, 45};
    std::sort(a, a + 3);
    std::cout << "second smallest value is: " << a[1] << std::endl;
}