在数组中查找第二大元素：详细代码实现

2021年3月12日15:15:07 发表评论 1,318 次浏览

本文概述

给定一个整数数组, 我们的任务是编写一个程序, 该程序可以有效地找到数组中存在的第二大元素。

例子：

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)。
    由于不需要额外的空间。
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: