C++ 我们如何有效地从数组中找到第二个最大值？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2392689/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How can we find second maximum from array efficiently?
提问by Xinus
Is it possible to find the second maximum number from an array of integers by traversing the array only once?
是否可以通过只遍历数组一次来从整数数组中找到第二个最大数？
As an example, I have a array of five integers from which I want to find second maximum number. Here is an attempt I gave in the interview:
例如，我有一个包含五个整数的数组，我想从中找到第二个最大数。这是我在采访中的一个尝试：
#define MIN -1
int main()
{
int max=MIN,second_max=MIN;
int arr[6]={0,1,2,3,4,5};
for(int i=0;i<5;i++){
cout<<"::"<<arr[i];
}
for(int i=0;i<5;i++){
if(arr[i]>max){
second_max=max;
max=arr[i];
}
}
cout<<endl<<"Second Max:"<<second_max;
int i;
cin>>i;
return 0;
}
The interviewer, however, came up with the test case int arr[6]={5,4,3,2,1,0};, which prevents it from going to the ifcondition the second time.
I said to the interviewer that the only way would be to parse the array two times (two forloops). Does anybody have a better solution?
然而，面试官想出了测试用例int arr[6]={5,4,3,2,1,0};，这阻止了它if第二次进入条件。我对面试官说，唯一的方法是解析数组两次（两次for循环）。有人有更好的解决方案吗？
回答by codaddict
Your initialization of maxand second_maxto -1is flawed. What if the array has values like {-2,-3,-4}?
您的max和second_maxto初始化-1有缺陷。如果数组有类似的值{-2,-3,-4}怎么办？
What you can do instead is to take the first 2 elements of the array (assuming the array has at least 2 elements), compare them, assign the smaller one to second_maxand the larger one to max:
你可以做的是取数组的前 2 个元素（假设数组至少有 2 个元素），比较它们，将较小的一个分配给second_max，将较大的一个分配给max：
if(arr[0] > arr[1]) {
second_max = arr[1];
max = arr[0];
} else {
second_max = arr[0];
max = arr[1];
}
Then start comparing from the 3rd element and update maxand/or second_maxas needed:
然后从第三个元素开始比较max并second_max根据需要更新和/或：
for(int i = 2; i < arr_len; i++){
// use >= n not just > as max and second_max can hav same value. Ex:{1,2,3,3}
if(arr[i] >= max){
second_max=max;
max=arr[i];
}
else if(arr[i] > second_max){
second_max=arr[i];
}
}
回答by avakar
The easiest solution would be to use std::nth_element.
最简单的解决方案是使用std::nth_element.
回答by Anders Abel
You need a second test:
您需要进行第二次测试：
for(int i=0;i<5;i++){
if(arr[i]>max){
second_max=max;
max=arr[i];
}
else if (arr[i] > second_max && arr[i] != max){
second_max = arr[i];
}
}
回答by Johann Gerell
Here you are:
这个给你：
std::pair<int, int> GetTwoBiggestNumbers(const std::vector<int>& array)
{
std::pair<int, int> biggest;
biggest.first = std::max(array[0], array[1]); // Biggest of the first two.
biggest.second = std::min(array[0], array[1]); // Smallest of the first two.
// Continue with the third.
for(std::vector<int>::const_iterator it = array.begin() + 2;
it != array.end();
++it)
{
if(*it > biggest.first)
{
biggest.second = biggest.first;
biggest.first = *it;
}
else if(*it > biggest.second)
{
biggest.second = *it;
}
}
return biggest;
}
回答by Hans Passant
Your original code is okay, you just have to initialize the max and second_max variables. Use the first two elements in the array.
你的原始代码没问题，你只需要初始化 max 和 second_max 变量。使用数组中的前两个元素。
回答by Martin
Quickselectis the way to go with this one. Pseudo code is available at that link so I shall just explain the overall algorithm:
快速选择是使用此方法的方法。该链接提供了伪代码，所以我将解释整个算法：
QuickSelect for kth largest number:
Select a pivot element
Split array around pivot
If (k < new pivot index)
perform quickselect on left hand sub array
else if (k > new pivot index)
perform quickselect on right hand sub array (make sure to offset k by size of lefthand array + 1)
else
return pivot
This is quite obviously based on the good old quicksort algorithm.
这很明显基于旧的快速排序算法。
Following this algorithm through, always selecting element zero as the pivot every time:
遵循这个算法，每次总是选择元素零作为主元：
select 4th largest number:
1) array = {1, 3, 2, 7, 11, 0, -4}
partition with 1 as pivot
{0, -4, _1_, 3, 2, 7, 11}
4 > 2 (new pivot index) so...
2) Select 1st (4 - 3) largest number from right sub array
array = {3, 2, 7, 11}
partition with 3 as pivot
{2, _3_, 7, 11}
1 < 2 (new pivot index) so...
3) select 1st largest number from left sub array
array = {2}
4) Done, 4th largest number is 2
This will leave your array in an undefined order afterwards, it's up to you if that's a problem.
之后这将使您的数组保持未定义的顺序，如果这是一个问题，这取决于您。
回答by Rajendra Uppal
Step 1. Decide on first two numbers.
Step 2. Loop through remaining numbers.
Step 3. Maintain latest maximum and second maximum.
Step 4. When updating second maximum, be aware that you are not making maximum and second maximum equal.
步骤 1. 决定前两个数字。
步骤 2. 遍历剩余的数字。
步骤 3. 保持最新的最大值和第二个最大值。
步骤 4. 更新第二个最大值时，请注意您没有使最大值和第二个最大值相等。
Tested for sorted input (ascending and descending), random input, input having duplicates, works fine.
测试排序输入（升序和降序）、随机输入、重复输入，工作正常。
#include <iostream>
#define MAX 50
int GetSecondMaximum(int* data, unsigned int size)
{
int max, secmax;
// Decide on first two numbers
if (data[0] > data[1])
{
max = data[0];
secmax = data[1];
}
else
{
secmax = data[0];
max = data[1];
}
// Loop through remaining numbers
for (unsigned int i = 2; i < size; ++i)
{
if (data[i] > max)
{
secmax = max;
max = data[i];
}
else if (data[i] > secmax && data[i] != max/*removes duplicate problem*/)
secmax = data[i];
}
return secmax;
}
int main()
{
int data[MAX];
// Fill with random integers
for (unsigned int i = 0; i < MAX; ++i)
{
data[i] = rand() % MAX;
std::cout << "[" << data[i] << "] "; // Display input
}
std::cout << std::endl << std::endl;
// Find second maximum
int nSecondMax = GetSecondMaximum(data, MAX);
// Display output
std::cout << "Second Maximum = " << nSecondMax << std::endl;
// Wait for user input
std::cin.get();
return 0;
}
回答by Boolean
Other way to solve this problem, is to use comparisons among the elements. Like for example,
解决这个问题的另一种方法是使用元素之间的比较。例如，
a[10] = {1,2,3,4,5,6,7,8,9,10}
Compare 1,2 and say max = 2 and second max = 1
比较 1,2 并说 max = 2 和 second max = 1
Now compare 3 and 4 and compare the greatest of them with max.
现在比较 3 和 4，并将它们中的最大值与最大值进行比较。
if element > max
second max = max
element = max
else if element > second max
second max = element
The advantage with this is, you are eliminating two numbers in just two comparisons.
这样做的好处是，您只需在两次比较中就消除了两个数字。
Let me know, if you have any problem understanding this.
让我知道，如果您在理解这一点上有任何问题。
回答by mitta
Check this solution.
检查此解决方案。
max1 = a[0];
max2 = a[1];
for (i = 1; i < n; i++)
{
if (max1 < a[i])
{
max2 = max1;
max1 = a[i];
}
if (max2 == max1) max2 = a[i + 1];
if (max2 == a[n])
{
printf("All numbers are the same no second max.\n");
return 0;
}
if (max2 < a[i] && max1 != a[i]) max2 = a[i];
}
回答by nikhil
Here is something which may work ,
这是可能有用的东西，
public static int secondLargest(int[] a){
int max=0;
int secondMax=0;
for(int i=0;i<a.length;i++){
if(a[i]<max){
if(a[i]>secondMax){
secondMax=a[i];
}
continue;
}
if(a[i]>max){
secondMax=max;
max=a[i];
}
}
return secondMax;
}
