我是一名新手,正在学习C++语言。现在我需要在一个数组中查找第二大的元素,但是我的代码有时候没有给出正确的输出。我有以下代码来查找第二个最大元素。
for(int i = 0;i<size;i++)
{
if(arr[i] > max)
{
second_max = max;
max = arr[i];
}
}
这段代码有时可以运行,但有时却无法给出第二大的元素正确的值。请帮我看看我做错了什么?
max: 15
second_max = 7
arr[i] = 12
if
条件语句下方添加以下条件:else if(arr[i] > second_max)
{
second_max = arr[i];
}
else if
,因为如果它大于 max
,那么它也将大于 second max
,除非有一个 else
,否则你会将两者都设置为 arr[i]
。此外,@MartinBonner,排序是过度的,线性解决方案也可以被证明是正确的。 - Glenn Teitelbaumarr[i]=20
,那么 arr[i]>max
,所以 second_max = 15; max =20
,然后 arr[i]>second max
,所以 second_max
也会被设置为 20。else
防止这种情况发生。 - Glenn Teitelbaum以下是一种仅使用标准算法的解决方案:
#include <iostream>
#include <vector>
#include <cassert>
int second_max(std::vector<int> v)
{
using namespace std;
sort(begin(v),
end(v),
std::greater<>());
auto last = unique(begin(v),
end(v));
auto size = last - begin(v);
return (size == 0)
? 0
: (size == 1)
? v[0]
: v[1];
}
int main()
{
using namespace std;
cout << second_max({ 3,5,7,7,2,4,3,2,6 }) << endl;
return 0;
}
nth_element
。 - LogicStuffstd::sort
,通常应该使用std::nth_element
来完成。这正是它设计的场景,并且在你只关心几个元素时避免了对整个集合进行排序。nth_element
的表现似乎比 partial_sort
差得多,但这可能是 VS2015 中的故障或我的基准测试中的错误 - 我必须在有时间时进行调查。 - MikeMB#include <array>
#include <algorithm>
#include <iostream>
int main()
{
std::array<int, 10> ar = {1, 5, 15, 2, 3, 5, 6, 8, 9, 14};
// Sort the array
std::sort(std::begin(ar), std::end(ar));
// Print the second max element
std::cout << ar[ar.size() - 2];
}
for(int i = 0; i<size; i++)
{
if(max < arr[i]) {
second_max = max;
max = arr[i];
}
else if(second_max < arr[i])
second_max = arr[i];
}
我的解决方案:
#include <stdio.h>
#include <limits.h>
/**
* get second max of array
* @param arr the Array
* @param len the array length
* @return return second max if searched otherwise return -1
*/
int getSecondMax(const int *arr, int len) {
int secondMax = INT_MIN; //-2147483647 - 1
int max = INT_MIN + 1;
for (int i = 0; i < len; ++i) {
if (arr[i] > max) {
secondMax = max;
max = arr[i];
} else if (arr[i] > secondMax && arr[i] != max) {
secondMax = arr[i];
}
}
return secondMax != INT_MIN + 1 ? secondMax : -1;
}
int main() {
int arr[] = {0, 3, -1, 4, 5};
int len = sizeof(arr) / sizeof(arr[0]);
int secondMax = getSecondMax(arr, len);
secondMax != -1 ? printf("the second max = %d\n", secondMax) : printf("not found second max\n");
return 0;
}
max
或second_max
。这可能是问题所在。 - erip{5, 5, 4}
,您想要5
还是4
? - Jarod42