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[ 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

• largest := -infinity

• secLargest := -infinity

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

  • 如果 e 大於 largest，則

    • largest = e

  • 結束 if

• 結束 for

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

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

    • secLargest = e

  • 結束 if

• 結束 for

• 返回 secLargest

示例

#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

• largest := A[0]

• 從 1 到 n - 1 開始索引遍歷，執行

  • 如果當前元素 A[ i ] 大於 largest，則

    • secLargest := largest

    • largest := A[ i ]

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

    • secLargest := A[ i ]

  • 結束 if

• 結束 for

• 返回 secLargest

示例

#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) 的時間。後來的解決方案效率更高，因為它們需要線性時間。第二個解決方案是使用雙重遍歷陣列來執行，這也可以透過單次遍歷進行最佳化，如第三個解決方案所示。