我想找到数组列表中的第二个最小值。这是我的代码。有更好的方法吗?
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) 时间复杂度。
这是对的吗?如果我错了,请有人纠正我
是的,它是 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
。如果您想以不同的方式处理重复项,只需稍作修改即可。
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
作为最小和第二小的数字。
#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)。
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) 时间内运行。
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;
}
算法:
#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;
}