Program C++ untuk mencari elemen kedua terbesar dalam tatasusunan

Tujuan tatasusunan adalah untuk menyimpan jenis data yang serupa dalam satu siri lokasi memori yang boleh diakses menggunakan alamat asas dan indeks. Kami menggunakan tatasusunan dalam banyak aplikasi yang berbeza untuk menyimpan data untuk pelbagai tujuan. Mencari elemen terkecil dan terbesar ialah contoh tatasusunan yang agak biasa, yang diperlukan dalam beberapa aplikasi termasuk pengisihan, dsb. Dalam artikel ini, kita akan belajar cara mencari elemen kedua terbesar daripada tatasusunan dalam C++.

Fahami konsep melalui contoh

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

Dalam contoh di atas, terdapat 12 elemen dalam tatasusunan. Elemen terbesar dalam tatasusunan ialah 99, dan elemen kedua terbesar ialah 89. Dalam kaedah pertama, untuk mencari elemen kedua terbesar, kita hanya perlu mengisih elemen dalam tertib menaik atau menurun, dan kemudian terus mengembalikan elemen kedua ke terakhir atau kedua untuk mendapatkan elemen kedua terbesar. Algoritmanya adalah seperti berikut -

Algoritma

• Dapatkan array A bersaiz n

• Isih tatasusunan A mengikut susunan nilainya yang tidak meningkat

• mengembalikan A[ 1 ] // kerana indeks ke-0 mengandungi elemen terbesar

Contoh

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

Output

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

Gunakan double traversal

Cara di atas nampak mudah, tetapi prosesnya tidak cekap untuk masalah ini. Memandangkan kami menggunakan pengisihan, melaksanakan pengisihan mengambil masa sekurang-kurangnya O(n.log n). Tetapi kita juga boleh menyelesaikan masalah ini dalam masa linear. Dalam kaedah semasa, kami mengulangi tatasusunan elemen dua kali dan mencari elemen kedua terbesar. Mari kita semak algoritma.

Algoritma

• Dapatkan array A bersaiz n

• Maksimum := -infiniti

• Max saat := -infiniti

• Untuk setiap elemen e dalam A, laksanakan

  • Jika e lebih besar daripada Maksimum, maka

    • maks = e

  • Tamat jika

• Tamat

• Untuk setiap elemen e dalam A, laksanakan

  • Jika e lebih besar daripada secTerbesar tetapi kurang daripada maksimum, maka

    • Maksimum saat = e

  • Tamat jika

• Tamat

• Kembali saat maksimum

Contoh

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

Output

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

Gunakan single traversal

Penyelesaian di atas berulang pada tatasusunan dua kali. Dalam larian pertama, cari elemen terbesar daripada tatasusunan, kemudian dalam larian kedua, cari elemen terbesar yang tidak lebih besar daripada terbesar pertama. Memandangkan tatasusunan ialah struktur data linear, setiap traversal mengambil masa O(n), jadi masa penyelesaian akhir ialah O(2n), yang juga linear, serupa dengan O(n). Tetapi ini bukan penyelesaian yang cekap, kita hanya boleh menyelesaikan masalah ini dengan satu laluan. Mari lihat algoritmanya.

Algoritma

• Dapatkan array A bersaiz n

• Maksimum := A[0]

• Untuk indeks permulaan dari 1 hingga n - 1, lakukan

  • Jika elemen semasa A[i] lebih besar daripada maksimum, maka

    • Maksimum saat := Maks

    • Maksimum := A[ i ]

  • Sebaliknya apabila A[ i ] berada di antara terbesar dan secTerbesar, maka

    • Maksimum saat := A[ i ]

  • Tamat jika

• Tamat

• Kembali saat maksimum

Contoh

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

Output

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

Kesimpulan

Dalam artikel ini, kami mempelajari tentang tiga cara berbeza untuk mencari elemen kedua terbesar daripada tatasusunan yang diberikan. Kaedah pertama ialah menggunakan pengisihan. Walau bagaimanapun, penyelesaian ini tidak cekap dan mengambil masa sekurang-kurangnya O(n log n). Penyelesaian yang terakhir adalah sangat cekap kerana ia memerlukan masa linear. Penyelesaian kedua ialah menggunakan hantaran berganda ke atas tatasusunan, yang juga boleh dioptimumkan dengan pas tunggal seperti yang ditunjukkan dalam penyelesaian ketiga.

Atas ialah kandungan terperinci Program C++ untuk mencari elemen kedua terbesar dalam tatasusunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!