本文概述
给定一个整数数组, 我们的任务是编写一个程序, 该程序可以有效地找到数组中存在的第二大元素。
例子:
Input: arr[] = {12, 35, 1, 10, 34, 1}
Output: The second largest element is 34.
Explanation: The largest element of the
array is 35 and the second
largest element is 34
Input: arr[] = {10, 5, 10}
Output: The second largest element is 5.
Explanation: The largest element of
the array is 10 and the second
largest element is 5
Input: arr[] = {10, 10, 10}
Output: The second largest does not exist.
Explanation: Largest element of the array
is 10 there is no second largest element
推荐:请在"
实践
首先, 在继续解决方案之前。
简单的解决方案
方法:
想法是按降序对数组进行排序, 然后返回第二个元素, 该元素不等于已排序数组中的最大元素。
C ++ 14
// C++ program to find second largest
// element in an array
#include <bits/stdc++.h>
using namespace std;
/* Function to print the second largest elements */
void print2largest( int arr[], int arr_size)
{
int i, first, second;
/* There should be atleast two elements */
if (arr_size < 2) {
printf ( " Invalid Input " );
return ;
}
// sort the array
sort(arr, arr + arr_size);
// start from second last element
// as the largest element is at last
for (i = arr_size - 2; i >= 0; i--) {
// if the element is not
// equal to largest element
if (arr[i] != arr[arr_size - 1]) {
printf ( "The second largest element is %d\n" , arr[i]);
return ;
}
}
printf ( "There is no second largest element\n" );
}
/* Driver program to test above function */
int main()
{
int arr[] = { 12, 35, 1, 10, 34, 1 };
int n = sizeof (arr) / sizeof (arr[0]);
print2largest(arr, n);
return 0;
}
Java
// Java program to find second largest
// element in an array
import java.util.*;
class GFG{
// Function to print the
// second largest elements
static void print2largest( int arr[], int arr_size)
{
int i, first, second;
// There should be
// atleast two elements
if (arr_size < 2 )
{
System.out.printf( " Invalid Input " );
return ;
}
// Sort the array
Arrays.sort(arr);
// Start from second last element
// as the largest element is at last
for (i = arr_size - 2 ; i >= 0 ; i--)
{
// If the element is not
// equal to largest element
if (arr[i] != arr[arr_size - 1 ])
{
System.out.printf( "The second largest " +
"element is %d\n" , arr[i]);
return ;
}
}
System.out.printf( "There is no second " +
"largest element\n" );
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 12 , 35 , 1 , 10 , 34 , 1 };
int n = arr.length;
print2largest(arr, n);
}
}
// This code is contributed by gauravrajput1
C#
// C# program to find second largest
// element in an array
using System;
class GFG{
// Function to print the
// second largest elements
static void print2largest( int []arr, int arr_size)
{
int i;
// There should be
// atleast two elements
if (arr_size < 2)
{
Console.Write( " Invalid Input " );
return ;
}
// Sort the array
Array.Sort(arr);
// Start from second last element
// as the largest element is at last
for (i = arr_size - 2; i >= 0; i--)
{
// If the element is not
// equal to largest element
if (arr[i] != arr[arr_size - 1])
{
Console.Write( "The second largest " +
"element is {0}\n" , arr[i]);
return ;
}
}
Console.Write( "There is no second " +
"largest element\n" );
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 12, 35, 1, 10, 34, 1 };
int n = arr.Length;
print2largest(arr, n);
}
}
// This code is contributed by Amit Katiyar
输出如下:
The second largest element is 34
复杂度分析:
- 时间复杂度:O(n log n)。
排序数组所需的时间为O(n log n)。 - 辅助空间:O(1)。
由于不需要额外的空间。
更好的解决方案:
方法:
方法是遍历数组两次。在第一个遍历中找到最大元素。在第二遍历中找到小于在第一遍历中获得的元素的最大元素。
C ++ 14
// C++ program to find second largest
// element in an array
#include <bits/stdc++.h>
using namespace std;
/* Function to print the second largest elements */
void print2largest( int arr[], int arr_size)
{
int i, first, second;
/* There should be atleast two elements */
if (arr_size < 2) {
printf ( " Invalid Input " );
return ;
}
int largest = second = INT_MIN;
// find the largest element
for ( int i = 0; i < arr_size; i++) {
largest = max(largest, arr[i]);
}
// find the second largest element
for ( int i = 0; i < arr_size; i++) {
if (arr[i] != largest)
second = max(second, arr[i]);
}
if (second == INT_MIN)
printf ( "There is no second largest element\n" );
else
printf ( "The second largest element is %d\n" , second);
}
/* Driver program to test above function */
int main()
{
int arr[] = { 12, 35, 1, 10, 34, 1 };
int n = sizeof (arr) / sizeof (arr[0]);
print2largest(arr, n);
return 0;
}
Java
// Java program to find second largest
// element in an array
class GFG{
// Function to print the second largest elements
static void print2largest( int arr[], int arr_size)
{
int i, first, second;
// There should be atleast two elements
if (arr_size < 2 )
{
System.out.printf( " Invalid Input " );
return ;
}
int largest = second = Integer.MIN_VALUE;
// Find the largest element
for (i = 0 ; i < arr_size; i++)
{
largest = Math.max(largest, arr[i]);
}
// Find the second largest element
for (i = 0 ; i < arr_size; i++)
{
if (arr[i] != largest)
second = Math.max(second, arr[i]);
}
if (second == Integer.MIN_VALUE)
System.out.printf( "There is no second " +
"largest element\n" );
else
System.out.printf( "The second largest " +
"element is %d\n" , second);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 12 , 35 , 1 , 10 , 34 , 1 };
int n = arr.length;
print2largest(arr, n);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to find
# second largest element
# in an array
# Function to print
# second largest elements
def print2largest(arr, arr_size):
# There should be atleast
# two elements
if (arr_size < 2 ):
print ( " Invalid Input " );
return ;
largest = second = - 2454635434 ;
# Find the largest element
for i in range ( 0 , arr_size):
largest = max (largest, arr[i]);
# Find the second largest element
for i in range ( 0 , arr_size):
if (arr[i] ! = largest):
second = max (second, arr[i]);
if (second = = - 2454635434 ):
print ( "There is no second " +
"largest element" );
else :
print ( "The second largest " +
"element is \n" , second);
# Driver code
if __name__ = = '__main__' :
arr = [ 12 , 35 , 1 , 10 , 34 , 1 ];
n = len (arr);
print2largest(arr, n);
# This code is contributed by shikhasingrajput
C#
// C# program to find second largest
// element in an array
using System;
class GFG{
// Function to print the second largest elements
static void print2largest( int []arr, int arr_size)
{
// int first;
int i, second;
// There should be atleast two elements
if (arr_size < 2)
{
Console.Write( " Invalid Input " );
return ;
}
int largest = second = int .MinValue;
// Find the largest element
for (i = 0; i < arr_size; i++)
{
largest = Math.Max(largest, arr[i]);
}
// Find the second largest element
for (i = 0; i < arr_size; i++)
{
if (arr[i] != largest)
second = Math.Max(second, arr[i]);
}
if (second == int .MinValue)
Console.Write( "There is no second " +
"largest element\n" );
else
Console.Write( "The second largest " +
"element is {0}\n" , second);
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 12, 35, 1, 10, 34, 1 };
int n = arr.Length;
print2largest(arr, n);
}
}
// This code is contributed by Amit Katiyar
输出如下:
The second largest element is 34
复杂度分析:
- 时间复杂度:上)。
需要两次遍历数组。 - 辅助空间:O(1)。
由于不需要额外的空间。
高效的解决方案
方法:
在单个遍历中查找第二大元素。
以下是完成此操作的完整算法:
1) Initialize two variables first and second to INT_MIN as
first = second = INT_MIN
2) Start traversing the array, a) If the current element in array say arr[i] is greater
than first. Then update first and second as, second = first
first = arr[i]
b) If the current element is in between first and second, then update second to store the value of current variable as
second = arr[i]
3) Return the value stored in second.
C
// C program to find second largest
// element in an array
#include <limits.h>
#include <stdio.h>
/* Function to print the second largest elements */
void print2largest( int arr[], int arr_size)
{
int i, first, second;
/* There should be atleast two elements */
if (arr_size < 2) {
printf ( " Invalid Input " );
return ;
}
first = second = INT_MIN;
for (i = 0; i < arr_size; i++) {
/* If current element is greater than first
then update both first and second */
if (arr[i] > first) {
second = first;
first = arr[i];
}
/* If arr[i] is in between first and
second then update second */
else if (arr[i] > second && arr[i] != first)
second = arr[i];
}
if (second == INT_MIN)
printf ( "There is no second largest element\n" );
else
printf ( "The second largest element is %dn" , second);
}
/* Driver program to test above function */
int main()
{
int arr[] = { 12, 35, 1, 10, 34, 1 };
int n = sizeof (arr) / sizeof (arr[0]);
print2largest(arr, n);
return 0;
}
C ++
// C++ program to find second largest
// element in an array
#include <bits/stdc++.h>
using namespace std;
// Function to print the second
// largest elements
void print2largest( int arr[], int arr_size)
{
int i, first, second;
// There should be atleast two elements
if (arr_size < 2)
{
cout << " Invalid Input " ;
return ;
}
first = second = INT_MIN;
for (i = 0; i < arr_size; i++)
{
// If current element is greater
// than first then update both
// first and second
if (arr[i] > first)
{
second = first;
first = arr[i];
}
// If arr[i] is in between first
// and second then update second
else if (arr[i] > second &&
arr[i] != first)
{
second = arr[i];
}
}
if (second == INT_MIN)
cout << "There is no second largest"
"element\n" ;
else
cout << "The second largest element is "
<< second;
}
// Driver code
int main()
{
int arr[] = { 12, 35, 1, 10, 34, 1 };
int n = sizeof (arr) / sizeof (arr[0]);
print2largest(arr, n);
return 0;
}
// This code is contributed by shivanisinghss2110
Java
// JAVA Code for Find Second largest
// element in an array
class GFG {
/* Function to print the second largest
elements */
public static void print2largest( int arr[], int arr_size)
{
int i, first, second;
/* There should be atleast two elements */
if (arr_size < 2 ) {
System.out.print( " Invalid Input " );
return ;
}
first = second = Integer.MIN_VALUE;
for (i = 0 ; i < arr_size; i++) {
/* If current element is smaller than
first then update both first and second */
if (arr[i] > first) {
second = first;
first = arr[i];
}
/* If arr[i] is in between first and
second then update second */
else if (arr[i] > second && arr[i] != first)
second = arr[i];
}
if (second == Integer.MIN_VALUE)
System.out.print( "There is no second largest"
+ " element\n" );
else
System.out.print( "The second largest element"
+ " is " + second);
}
/* Driver program to test above function */
public static void main(String[] args)
{
int arr[] = { 12 , 35 , 1 , 10 , 34 , 1 };
int n = arr.length;
print2largest(arr, n);
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python program to
# find second largest
# element in an array
# Function to print the
# second largest elements
def print2largest(arr, arr_size):
# There should be atleast
# two elements
if (arr_size < 2 ):
print ( " Invalid Input " )
return
first = second = - 2147483648
for i in range (arr_size):
# If current element is
# smaller than first
# then update both
# first and second
if (arr[i] > first):
second = first
first = arr[i]
# If arr[i] is in
# between first and
# second then update second
elif (arr[i] > second and arr[i] ! = first):
second = arr[i]
if (second = = - 2147483648 ):
print ( "There is no second largest element" )
else :
print ( "The second largest element is" , second)
# Driver program to test
# above function
arr = [ 12 , 35 , 1 , 10 , 34 , 1 ]
n = len (arr)
print2largest(arr, n)
# This code is contributed
# by Anant Agarwal.
C#
// C# Code for Find Second largest
// element in an array
using System;
class GFG {
// Function to print the
// second largest elements
public static void print2largest( int [] arr, int arr_size)
{
int i, first, second;
// There should be atleast two elements
if (arr_size < 2) {
Console.WriteLine( " Invalid Input " );
return ;
}
first = second = int .MinValue;
for (i = 0; i < arr_size; i++) {
// If current element is smaller than
// first then update both first and second
if (arr[i] > first) {
second = first;
first = arr[i];
}
// If arr[i] is in between first
// and second then update second
else if (arr[i] > second && arr[i] != first)
second = arr[i];
}
if (second == int .MinValue)
Console.Write( "There is no second largest"
+ " element\n" );
else
Console.Write( "The second largest element"
+ " is " + second);
}
// Driver Code
public static void Main(String[] args)
{
int [] arr = { 12, 35, 1, 10, 34, 1 };
int n = arr.Length;
print2largest(arr, n);
}
}
// This code is contributed by Parashar.
的PHP
<?php
// PHP program to find second largest
// element in an array
// Function to print the
// second largest elements
function print2largest( $arr , $arr_size )
{
// There should be atleast
// two elements
if ( $arr_size < 2)
{
echo ( " Invalid Input " );
return ;
}
$first = $second = PHP_INT_MIN;
for ( $i = 0; $i < $arr_size ; $i ++)
{
// If current element is
// smaller than first
// then update both
// first and second
if ( $arr [ $i ] > $first )
{
$second = $first ;
$first = $arr [ $i ];
}
// If arr[i] is in
// between first and
// second then update
// second
else if ( $arr [ $i ] > $second &&
$arr [ $i ] != $first )
$second = $arr [ $i ];
}
if ( $second == PHP_INT_MIN)
echo ( "There is no second largest element\n" );
else
echo ( "The second largest element is " . $second . "\n" );
}
// Driver Code
$arr = array (12, 35, 1, 10, 34, 1);
$n = sizeof( $arr );
print2largest( $arr , $n );
// This code is contributed by Ajit.
?>
输出如下:
The second largest element is 34
复杂度分析:
- 时间复杂度:上)。
只需遍历数组。 - 辅助空间:O(1)。
由于不需要额外的空间。