Comment pouvons-nous trouver une deuxième maximale de la matrice de manière efficace?

Votre initialisation de max et second_max à -1 est erronée. Que faire si la matrice a des valeurs comme { -2,-3,-4}?

Ce que vous pouvez faire à la place est de prendre les 2 premiers éléments de la matrice (en supposant que la matrice a au moins 2 éléments), de les comparer, d'attribuer la plus petite à second_max et la plus grande pour max:

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

Puis commencer à comparer à partir de la 3ème élément et mise à jour max et/ou second_max tant que de besoin:

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

Vous avez besoin d'un deuxième 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];
   }
 }

Vous êtes ici:

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

L'étape 1. Décider sur les deux premiers numéros.

Étape 2. Boucle par le biais de numéros restants.

Étape 3. Maintenir plus tard maximale et la seconde maximum.

Étape 4. Lors de la mise à jour de seconde maximum, sachez que vous ne faites pas de maximum et de la deuxième maximum égal.

Testé pour entrée triée (ascendant et descendant), aléatoire d'entrée, entrée en ayant des doublons, fonctionne très bien.

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

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

La limite supérieure doit avoir n+log2⁡n−2, mais plus grand que O(n) dans le cas de la sélection aléatoire de l'algorithme, mais dans le pire des cas, il est beaucoup plus petit. La solution pourrait être

1. construire un arbre comme pour trouver le MAX de l'élément n - 1 comparaisons

   max(N)
   /\
   max(N/2) max(N/2)

2. retirer le MAX et de trouver le MAX de nouveau log2n - 1 comparaison

PS. Il utilise de la mémoire supplémentaire, mais il plus rapide que la sélection aléatoire de l'algorithme dans le pire cas.

Comment au sujet de la suite ci-dessous.
make_heap est O(n) donc, c'est efficace et c'est 1 passe
Nous trouvons le second max par prendre avantage qu'il doit être l'un des tas des enfants de la mère, qui avait le maximum.

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

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