我是一名新手，正在学习C++语言。现在我需要在一个数组中查找第二大的元素，但是我的代码有时候没有给出正确的输出。我有以下代码来查找第二个最大元素。
for(int i = 0;i<size;i++)
{
if(arr[i] > max)
{
second_max = max;
max = arr[i];
}
}
这段代码有时可以运行，但有时却无法给出第二大的元素正确的值。请帮我看看我做错了什么？
6个回答
8
假设你正在查找数组中的最大值和第二大值，我注意到你跳过了当 `arr[i]` 大于 `second_max` 但小于 `max` 的情况。例如对于以下场景，你的代码将无法正常工作。
在第一个
max: 15
second_max = 7
arr[i] = 12
在第一个
if条件语句下方添加以下条件：else if(arr[i] > second_max)
{
second_max = arr[i];
}
- Itban Saeed
3
虽然这个方法可以运行，但我认为使用排序的解决方案更加健壮。显然是正确的（扩展到“第三大”等也很明显）。当然，对于大输入，排序会更慢。 - Martin Bonner supports Monica
这应该是
else if，因为如果它大于 max，那么它也将大于 second max，除非有一个 else，否则你会将两者都设置为 arr[i]。此外，@MartinBonner，排序是过度的，线性解决方案也可以被证明是正确的。 - Glenn Teitelbaum如果
arr[i]=20，那么 arr[i]>max，所以 second_max = 15; max =20，然后 arr[i]>second max，所以 second_max 也会被设置为 20。else 防止这种情况发生。 - Glenn Teitelbaum5
以下是一种仅使用标准算法的解决方案：
#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;
}
- Richard Hodges
4
@LogicStuff 我在标准中或cppreference页面上没有看到这个要求。http://en.cppreference.com/w/cpp/algorithm/unique - Richard Hodges
@LogicStuff：它不需要排序范围。有时您只想删除_连续_重复项，而不是_所有_重复项。 - Blastfurnace
表述有误...我认为你需要移除所有最大元素的重复项才能得到正确的
nth_element。 - LogicStuff3
与其使用
std::sort，通常应该使用std::nth_element来完成。这正是它设计的场景，并且在你只关心几个元素时避免了对整个集合进行排序。- Jerry Coffin
7
@MikeMB：你可以使用partial_sort，但是使用它来查找最大元素也不是很容易--至少对我来说不是显而易见的巨大改进。无论如何，我们已经远离了最初的问题。 - Jerry Coffin
@JerryCoffin：从未说过这是一个巨大的改进，但它可以少打一行代码（或减少50%的输入），并且可能（我不知道具体实现）更高效。 - MikeMB
@MikeMB：这不太可能更有效（我已经查看了实现）。如果你使用反向迭代器和std::greater来获取顶部的最大项，它也不太可能明显缩短。 - Jerry Coffin
此外，由于某种原因，在我的机器上，
nth_element 的表现似乎比 partial_sort 差得多，但这可能是 VS2015 中的故障或我的基准测试中的错误 - 我必须在有时间时进行调查。 - MikeMB显示剩余2条评论
0
你可以使用这个小程序。我只使用了标准算法，这是我能想到的最简单的方法。
#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];
}
- TheCrafter
2
如果arr.size()小于2会发生什么？ - Gian Lorenzo Meocci
如果arr.size()小于2，你不需要使用std来找到第二大的元素！编写这个例子时，考虑到他将拥有一个静态数组而不是向量。 - TheCrafter
0
你的if语句逻辑不完整。这是可用的版本：
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];
}
- gregb
0
我的解决方案：
#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;
}
- duyuanchao
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
max或second_max。这可能是问题所在。 - erip{5, 5, 4}，您想要5还是4？ - Jarod42