C++程式以尋找數組中第二大的元素

陣列的目的是將相似類型的資料儲存在一系列可以使用基底位址和索引存取的記憶體位置中。我們在許多不同的應用程式中使用陣列來保存用於各種目的的資料。找到最小和最大元素是數組的一個相當常見的範例，在包括排序等在內的多個應用程式中都需要數組。在本文中，我們將了解如何在 C 中從陣列中找到第二大元素。

透過範例理解概念

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

在上面的範例中，陣列中有 12 個元素。數組中最大的元素是99，第二大的元素是89。在第一種方法中要找到第二大的元素，我們只需將元素按升序或降序排序，然後直接返回倒數第二個或第二個元素以獲得第二大元素。演算法如下 -

演算法

• 取大小為n的陣列A

• 根據陣列 A 的值的非遞增順序對陣列 A 進行排序

• 傳回 A[ 1 ] // 因為第 0 個索引包含最大元素

#範例

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

輸出

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

使用雙重遍歷

上面的方法看起來很簡單，但是這個過程對於這個問題來說效率不高。由於我們使用排序，因此執行排序至少需要 O(n.log n) 時間。但我們也可以在線性時間內解決這個問題。在目前的方法中，我們兩次遍歷元素數組並找到第二大元素。讓我們檢查一下演算法。

演算法

• 取大小為n的陣列A

• 最大 := -無窮大

• 秒最大 := -無窮大

• 對於 A 中的每個元素 e，執行

  • 如果 e 大於 Maximum，則

    • 最大= e

  • #結束如果

• 結束

• #對於 A 中的每個元素 e，執行

  • 如果e大於secLargest但小於maximum，則

    • 秒最大= e

  • #結束如果

• 結束

• #傳回秒最大

#範例

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

輸出

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

使用單次遍歷

上面的解決方案遍歷了陣列兩次。在第一次運行中，從數組中找到最大的元素，然後在第二次運行中，搜尋最大但不大於第一個最大的元素。由於陣列是線性資料結構，每次遍歷都需要 O(n) 時間，因此最終求解的時間為 O(2n)，也是線性的，與 O(n) 類似。但這不是一個有效的解決方案，我們只能透過一次遍歷來解決這個問題。讓我們看看它的演算法。

演算法

• 取大小為n的陣列A

• 最大 := A[0]

• 對於從 1 到 n - 1 的起始索引，執行

  • 如果目前元素A[ i ]大於maximum，則

    • 秒最大 := 最大

    • 最大 := A[ i ]

  • 否則當 A[ i ] 介於largest 和 secLargest 之間時，則

    • 秒最大 := A[ i ]

  • 結束如果

• 結束

• #傳回秒最大

#範例

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

輸出

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

結論

在本文中，我們了解了從給定數組中尋找第二大元素的三種不同方法。第一種方法是使用排序。然而，這個解決方案效率不高，並且至少需要 O(n log n ) 時間。後一種解決方案非常有效，因為它們需要線性時間。第二種解決方案是在陣列上使用雙重遍歷，也可以透過單一遍歷進行最佳化，如第三種解決方案所示。

以上是C++程式以尋找數組中第二大的元素的詳細內容。更多資訊請關注PHP中文網其他相關文章！