如何有效地从数组中找到第二个最大值?

max 和 second_max -1 是有缺陷的。如果数组的值 {-2,-3,-4} ?

你可以做的是取数组的前2个元素(假设数组至少有2个元素),比较它们,将较小的元素分配给 第二个最大值 再大一点的 :

if(arr[0] > arr[1]) {
 second_max = arr[1];
 max = arr[0];
} else {
 second_max = arr[0];
 max = arr[1];
}

最大值 根据需要:

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

最简单的解决办法是 std::nth_element .

您需要进行第二次测试:

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

您的原始代码是好的,您只需初始化max和second\u max变量。使用数组中的前两个元素。

给你:

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

Quickselect 就是这条路。伪代码在该链接中可用,因此我将解释整个算法:

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

遵循此算法,每次始终选择元素0作为轴:

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

第一步,决定前两个数字。
第二步,循环剩余的数字。
步骤3.保持最新最大值和第二最大值。

测试排序输入(升序和降序),随机输入,输入有重复,工作良好。

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

解决这个问题的另一种方法是使用元素之间的比较。比如说,

a[10] = {1,2,3,4,5,6,7,8,9,10}

if element > max
     second max = max
     element = max
else if element > second max
     second max = element

这样做的好处是,您可以在两次比较中消除两个数字。

检查此解决方案。

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

这里有些东西可能有用,

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

上界应该是n+log2n2,但在随机选择算法中它比O(n)大,但在最坏的情况下它要小得多。解决办法可能是

1. 最大值(N) / \ 最大(N/2)最大(N/2)

2. 删除最大值并再次找到最大值log2n-1比较

我们不能按降序排序,从排序后的数组中取第二个元素吗?

下面的怎么样。 make_heap是O(n),所以这是有效的,这是1-pass

#include <algorithm>
#include <iostream>

int main()
{
    int arr[6]={0,1,2,3,4,5};

    std::make_heap(arr, arr+6);
    std::cout << "First Max: " << arr[0] << '\n';
    std::cout << "Second Max: " << std::max(arr[1], arr[2]) << '\n';
    return 0;
}

int max,secondMax;
max=secondMax=array[0];
                                                for(int i=0;i<array.length;i++)
    {                                                   if(array[i]>max)                                                    {                                           max=array[i];                                                   }
                                                        if(array[i]>secondMax && array[i]<max)                                                  {
    secondMax=array[i];                                                 }
    }

#include <iostream>
using namespace std;

int main() {

   int  max = 0;
    int sec_Max = 0;

    int array[] = {81,70,6,78,54,77,7,78};

    int loopcount = sizeof(array)/sizeof(int);

    for(int i = 0 ; i < loopcount ; ++i)
    {

        if(array[i]>max)
        {
            sec_Max = max;
            max = array[i];
        }

        if(array[i] > sec_Max && array[i] < max)
        {
            sec_Max = array[i];
        }
    }

    cout<<"Max:" << max << " Second Max: "<<sec_Max<<endl;

    return 0;
}

// Set the first two different numbers as the maximum and second maximum numbers

 int max = array[0];
 int i = 1;
//n is the amount of numbers

 while (array[i] == max && i < n) i++;
 int sec_max = array[i];
 if( max < sec_max ) {
    tmp = sec_max;
    sec_max = max;
    max = tmp;
 }

//find the second maximum number

 for( ; i < n; ++i ) {
   if( array[i] > max ) {
     sec_max = max;
     max = array[i];
   } else if( array[i] > sec_max && array[i] != max ) {
     sec_max = array[i];
   }
 }
 printf("The second maximum number is %d\n", sec_max);