C++-Programm zum Finden des zweitgrößten Elements in einem Array

Der Zweck eines Arrays besteht darin, ähnliche Datentypen in einer Reihe von Speicherorten zu speichern, auf die über Basisadressen und Indizes zugegriffen werden kann. Wir verwenden Arrays in vielen verschiedenen Anwendungen, um Daten für verschiedene Zwecke zu speichern. Das Finden der kleinsten und größten Elemente ist ein recht häufiges Beispiel für Arrays, die in verschiedenen Anwendungen benötigt werden, einschließlich Sortieren usw. In diesem Artikel erfahren Sie, wie Sie in C++ das zweitgrößte Element aus einem Array finden.

Konzepte anhand von Beispielen verstehen

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

Im obigen Beispiel gibt es 12 Elemente im Array. Das größte Element im Array ist 99 und das zweitgrößte Element ist 89. Um das zweitgrößte Element zu finden, müssen wir bei der ersten Methode nur die Elemente in aufsteigender oder absteigender Reihenfolge sortieren und dann direkt das vorletzte oder zweite Element zurückgeben, um das zweitgrößte Element zu erhalten. Der Algorithmus ist wie folgt -

Algorithmus

• Erhalten Sie ein Array A der Größe n

• Sortieren Sie Array A nach nicht aufsteigender Reihenfolge seiner Werte

• gibt A[ 1 ] zurück // weil der 0. Index das größte Element enthält

Beispiel

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

Ausgabe

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

Verwenden Sie die doppelte Durchquerung

Die obige Methode scheint einfach zu sein, aber der Prozess ist für dieses Problem nicht effizient. Da wir die Sortierung verwenden, dauert die Sortierung mindestens O(n.log n) Zeit. Wir können dieses Problem aber auch in linearer Zeit lösen. Bei der aktuellen Methode durchlaufen wir das Array der Elemente zweimal und finden das zweitgrößte Element. Lassen Sie uns den Algorithmus überprüfen.

Algorithmus

• Erhalten Sie ein Array A der Größe n

• Maximum := -unendlich

• Maximale Sekunden := -unendlich

• Führen Sie für jedes Element e in A

  aus

  • Wenn e größer als Maximum ist, dann

    • max = e

  • Ende wenn

• Ende

• Führen Sie für jedes Element e in A

  aus

  • Wenn e größer als secLargest, aber kleiner als Maximum ist, dann

    • Sekunden max = e

  • Ende wenn

• Ende

• Maximale Sekunden zurückgeben

Beispiel

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

Ausgabe

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

Verwenden Sie eine einzelne Durchquerung

Die obige Lösung durchläuft das Array zweimal. Suchen Sie im ersten Durchlauf das größte Element aus dem Array und im zweiten Durchlauf das größte Element, das nicht größer als das erste größte ist. Da es sich bei dem Array um eine lineare Datenstruktur handelt, benötigt jeder Durchlauf O(n) Zeit, sodass die endgültige Lösungszeit O(2n) beträgt, die ebenfalls linear ist, ähnlich wie O(n). Dies ist jedoch keine effiziente Lösung. Wir können dieses Problem nur in einem Durchgang lösen. Sehen wir uns seinen Algorithmus an.

Algorithmus

• Erhalten Sie ein Array A der Größe n

• Maximum := A[0]

• Für einen Startindex von 1 bis n - 1 machen Sie

  • Wenn das aktuelle Element A[i] größer als das Maximum ist, dann

    • Sekunden max := Max

    • Maximum := A[ i ]

  • Ansonsten, wenn A[ i ] zwischen dem größten und dem zweiten größten liegt, dann

    • Maximale Sekunden := A[ i ]

  • Ende wenn

• Ende

• Maximale Sekunden zurückgeben

Beispiel

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

Ausgabe

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

Fazit

In diesem Artikel haben wir drei verschiedene Möglichkeiten kennengelernt, um das zweitgrößte Element aus einem bestimmten Array zu finden. Die erste Methode ist die Sortierung. Diese Lösung ist jedoch nicht effizient und benötigt mindestens O(n log n ) Zeit. Letztere Lösungen sind sehr effizient, da sie lineare Zeit benötigen. Die zweite Lösung besteht darin, einen doppelten Durchgang über das Array zu verwenden, der auch mit einem einzigen Durchgang optimiert werden kann, wie in der dritten Lösung gezeigt.

Das obige ist der detaillierte Inhalt vonC++-Programm zum Finden des zweitgrößten Elements in einem Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!