数组的目的是将相似类型的数据存储在一系列可以使用基地址和索引访问的内存位置中。我们在许多不同的应用程序中使用数组来保存用于各种目的的数据。查找最小和最大元素是数组的一个相当常见的示例，在包括排序等在内的多个应用程序中都需要数组。在本文中，我们将了解如何在 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 进行排序
立即学习“C++免费学习笔记（深入）”；
返回 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 ) 时间。后一种解决方案非常有效，因为它们需要线性时间。第二种解决方案是在数组上使用双重遍历，也可以通过单次遍历进行优化，如第三种解决方案所示。
