Programme C++ pour trouver le deuxième plus grand élément d'un tableau

Le but d'un tableau est de stocker des types de données similaires dans une série d'emplacements mémoire accessibles à l'aide d'adresses de base et d'index. Nous utilisons des tableaux dans de nombreuses applications différentes pour conserver des données à diverses fins. La recherche des éléments les plus petits et les plus grands est un exemple assez courant de tableaux, nécessaires dans plusieurs applications, notamment le tri, etc. Dans cet article, nous apprendrons comment trouver le deuxième plus grand élément d’un tableau en C++.

Comprendre les concepts à travers des exemples

Given array A = [89, 12, 32, 74, 14, 69, 45, 12, 99, 85, 63, 32]
The second largest element is 89

Dans l'exemple ci-dessus, il y a 12 éléments dans le tableau. Le plus grand élément du tableau est 99 et le deuxième plus grand élément est 89. Dans la première méthode, pour trouver le deuxième plus grand élément, il suffit de trier les éléments par ordre croissant ou décroissant, puis de renvoyer directement l'avant-dernier ou le deuxième élément pour obtenir le deuxième plus grand élément. L'algorithme est le suivant -

Algorithme

• Obtenez un tableau A de taille n

• Trier le tableau A selon l'ordre non croissant de ses valeurs

• renvoie A[ 1 ] // car le 0ème index contient le plus grand élément

Exemple

#include <iostream>
#include <algorithm>
# define Z 30

using namespace std;

void displayArr(int arr[], int n ) {
   for( int i = 0; i < n; i++ ){
      cout << arr[ i ] << ", ";
   } 
   cout << endl;
} 

int getSecondLargest( int A[], int n ){
   sort( A, A + n, greater<int>() );
   return A[ 1 ];
}

int main() {
   int arr[ Z ] = {84, 56, 21, 32, 74, 96, 85, 41, 21, 94, 20, 37, 36, 75, 20};
   int n = 15;
   
   cout << "Given array elements: ";
   displayArr( arr, n);
   
   cout << "The second largest element: " << getSecondLargest( arr, n ); 
}

Sortie

Given array elements: 84, 56, 21, 32, 74, 96, 85, 41, 21, 94, 20, 37, 36, 75, 20, 
The second largest element: 94

Utilisez la double traversée

La méthode ci-dessus semble simple, mais le processus n'est pas efficace pour ce problème. Puisque nous utilisons le tri, effectuer le tri prend au moins un temps O(n.log n). Mais on peut aussi résoudre ce problème en temps linéaire. Dans la méthode actuelle, nous parcourons deux fois le tableau d’éléments et trouvons le deuxième plus grand élément. Vérifions l'algorithme.

Algorithme

• Obtenez un tableau A de taille n

• Maximum := -infini

• Max secondes := -infini

• Pour chaque élément e dans A, exécutez

  • Si e est supérieur au Maximum, alors

    • max = e

  • Fin si

• Fin

• Pour chaque élément e dans A, exécutez

  • Si e est supérieur à secLargest mais inférieur au maximum, alors

    • Secondes max = e

  • Fin si

• Fin

• Retour en secondes maximum

Exemple

#include <iostream>
#include <algorithm>
# define Z 30

using namespace std;

void displayArr(int arr[], int n ) {
   for( int i = 0; i < n; i++ ){
      cout << arr[ i ] << ", ";
   } 
   cout << endl;
} 

int getSecondLargest( int A[], int n ){
   int largest = -99999;
   for( int i = 0; i < n; i++ ) {
      if( A[i] > largest ){
         largest = A [ i ]; 
      }   
   }
   int secLargest = -99999;
   for( int i = 0; i < n; i++ ) {
      if( A[i] > secLargest && A[i] < largest ){
         secLargest = A [ i ]; 
      }   
   }
   return secLargest;
}

int main() {
   int arr[ Z ] = {84, 56, 21, 32, 74, 96, 85, 41, 21, 94, 20, 37, 36, 75, 20};
   int n = 15;
   
   cout << "Given array elements: ";
   displayArr( arr, n);
   
   cout << "The second largest element: " << getSecondLargest( arr, n ); 
}

Sortie

Given array elements: 84, 56, 21, 32, 74, 96, 85, 41, 21, 94, 20, 37, 36, 75, 20, 
The second largest element: 94

Utiliser une traversée unique

La solution ci-dessus parcourt le tableau deux fois. Lors de la première exécution, recherchez le plus grand élément du tableau, puis lors de la deuxième exécution, recherchez le plus grand élément qui n'est pas plus grand que le premier plus grand. Puisque le tableau est une structure de données linéaire, chaque parcours prend un temps O(n), donc le temps de solution final est O(2n), qui est également linéaire, similaire à O(n). Mais ce n’est pas une solution efficace, nous ne pouvons résoudre ce problème qu’en un seul passage. Voyons son algorithme.

Algorithme

• Prenez un tableau A de taille n

• Maximum := A[0]

• Pour un indice de départ de 1 à n - 1, faites

  • Si l'élément actuel A[i] est supérieur au maximum, alors

    • Secondes max := Max

    • Maximum := A[ i ]

  • Sinon, lorsque A[ i ] est compris entre plus grand et secLargest, alors

    • Secondes maximales := A[ i ]

  • Fin si

• Fin

• Retour en secondes maximum

Exemple

#include <iostream>
#include <algorithm>
# define Z 30

using namespace std;

void displayArr(int arr[], int n ) {
   for( int i = 0; i < n; i++ ){
      cout << arr[ i ] << ", ";
   } 
   cout << endl;
} 

int getSecondLargest( int A[], int n ){
   int largest = A[ 0 ];
   int secLargest = -9999;
   for( int i = 1; i < n; i++ ) {
      if( A[i] > largest ){
         secLargest = largest; 
         largest = A[ i ];
      }   
      else if( secLargest < A[ i ] && A[ i ] != largest ) {
         secLargest = A[ i ];
      }
   } 
   return secLargest;
}

int main() {
   int arr[ Z ] = {84, 56, 21, 32, 74, 96, 85, 41, 21, 94, 20, 37, 36, 75, 20};
   int n = 15;
   
   cout << "Given array elements: ";
   displayArr( arr, n);
   
   cout << "The second largest element: " << getSecondLargest( arr, n ); 
}

Sortie

Given array elements: 84, 56, 21, 32, 74, 96, 85, 41, 21, 94, 20, 37, 36, 75, 20, 
The second largest element: 94

Conclusion

Dans cet article, nous avons découvert trois façons différentes de trouver le deuxième plus grand élément d'un tableau donné. La première méthode consiste à utiliser le tri. Cependant, cette solution n’est pas efficace et prend au moins un temps O(n log n ). Ces dernières solutions sont très efficaces car elles nécessitent un temps linéaire. La deuxième solution consiste à utiliser un double passage sur le tableau, qui peut également être optimisé en un seul passage, comme le montre la troisième solution.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!