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) 的时间。后来的解决方案效率更高，因为它们需要线性时间。第二个解决方案是使用双重遍历数组来执行，这也可以通过单次遍历进行优化，如第三个解决方案所示。