找到第二个最小值

问题描述 投票:0回答:6

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

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) 时间复杂度。
这是对的吗?如果我错了,请有人纠正我

c++ arrays time-complexity minimum
6个回答
7
投票

是的,它 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

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


6
投票
可以使用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)


1
投票
你可以用一个循环来处理它:

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) 时间内运行。


1
投票
您可以在循环的一次迭代中完成此操作:

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; }
    

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

算法:

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

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

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

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

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


0
投票
可以对数组进行升序排序,得到第二个元素:

#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; }
    
© www.soinside.com 2019 - 2024. All rights reserved.