Dada una array arr[] que consta de N enteros, la tarea es encontrar el segundo elemento más grande en la array dada usando N+log 2 (N) – 2 comparaciones.
Ejemplos:
Entrada : arr[] = {22, 33, 14, 55, 100, 12}
Salida : 55Entrada : arr[] = {35, 23, 12, 35, 19, 100}
Salida : 35
Ordenación y enfoque de dos recorridos: Consulte Encontrar el segundo elemento más grande en una array para obtener soluciones usando Ordenar y atravesar la array dos veces.
Enfoque eficiente:
siga los pasos a continuación para resolver el problema:
- Encuentre el elemento más grande de la array dada y realice un seguimiento de todos los elementos en comparación con el elemento más grande.
- Divida la array actual en dos subarreglos de igual longitud.
- Para cada subarreglo, busque recursivamente el elemento más grande y devuelva un arreglo en el que el primer índice contiene la longitud de este arreglo, el segundo elemento de índice contiene el elemento más grande y el resto del arreglo contiene los elementos con los que se ha comparado el elemento más grande.
- Ahora, a partir de los dos arreglos devueltos por ambos subarreglos, compare el elemento más grande de ambos subarreglos y devuelva el arreglo que contiene el mayor de los dos.
- La array final devuelta por findLargest() contiene su tamaño en el primer índice, el elemento más grande de la array en el segundo índice y los elementos comparados con el elemento más grande en los índices restantes. Repita los pasos anteriores usando findLargest() para encontrar el segundo elemento más grande de la array de la lista de elementos comparados.
Análisis del algoritmo:
Es claramente visible a partir del algoritmo que la complejidad temporal del algoritmo findLargest() es O(N) [N: tamaño de la array]
Por lo tanto, se realizan (N-1) comparaciones .
Ahora, el tamaño de la array devuelta por findLargest() es log 2 (N) + 2, de los cuales log 2 (N) elementos son aquellos con los que se compara el elemento más grande .
Por lo tanto, para encontrar el segundo elemento más grande, el más grande entre estos elementos log 2 (N) se calcula usando log 2(N) – 1 comparaciones.Por lo tanto, el número total de comparaciones = N – 1 + log 2 (N) – 1 = N + log 2 (N) – 2
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the largest
// element in the array arr[]
vector<int> findLargest(int beg, int end,
vector<int> arr, int n)
{
// Base Condition
if (beg == end)
{
// Initialize an empty list
vector<int> compared(n, 0);
compared[0] = 1;
compared[1] = arr[beg];
return compared;
}
// Divide the array into two equal
// length subarrays and recursively
// find the largest among the two
vector<int> compared1 = findLargest(
beg, (beg + end) / 2,
arr, n);
vector<int> compared2 = findLargest(
(beg + end) / 2 + 1,
end, arr, n);
if (compared1[1] > compared2[1])
{
int k = compared1[0] + 1;
// Store length of compared1[]
// in the first index
compared1[0] = k;
// Store the maximum element
compared1[k] = compared2[1];
// Return compared1 which
// contains the maximum element
return compared1;
}
else
{
int k = compared2[0] + 1;
// Store length of compared2[]
// in the first index
compared2[0] = k;
// Store the maximum element
compared2[k] = compared1[1];
// Return compared2[] which
// contains the maximum element
return compared2;
}
}
// Function to print the second largest
// element in the array arr[]
void findSecondLargest(int end, vector<int> arr)
{
// Find the largest element in arr[]
vector<int> compared1 = findLargest(
0, end - 1, arr, end);
// Find the second largest element
// in arr[]
vector<int> compared2 = findLargest(
2, compared1[0] + 2,
compared1,
compared1[0]);
// Print the second largest element
cout << compared2[1];
}
// Driver code
int main()
{
int N = 10;
vector<int> arr{ 20, 1990, 12, 1110, 1,
59, 12, 15, 120, 1110};
findSecondLargest(N, arr);
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Function to find the largest
// element in the array arr[]
static int[] findLargest(int beg, int end,
int []arr, int n)
{
// Base Condition
if (beg == end)
{
// Initialize an empty list
int []compared = new int[n];
compared[0] = 1;
compared[1] = arr[beg];
return compared;
}
// Divide the array into two equal
// length subarrays and recursively
// find the largest among the two
int []compared1 = findLargest(beg,
(beg + end) /
2, arr, n);
int []compared2 = findLargest((beg + end) /
2 + 1,
end, arr, n);
if (compared1[1] > compared2[1])
{
int k = compared1[0] + 1;
// Store length of compared1[]
// in the first index
compared1[0] = k;
// Store the maximum element
compared1[k] = compared2[1];
// Return compared1 which
// contains the maximum element
return compared1;
}
else
{
int k = compared2[0] + 1;
// Store length of compared2[]
// in the first index
compared2[0] = k;
// Store the maximum element
compared2[k] = compared1[1];
// Return compared2[] which
// contains the maximum element
return compared2;
}
}
// Function to print the second largest
// element in the array arr[]
static void findSecondLargest(int end,
int []arr)
{
// Find the largest element in arr[]
int []compared1 = findLargest(0, end - 1,
arr, end);
// Find the second largest element
// in arr[]
int []compared2 = findLargest(2, compared1[0] + 2,
compared1,
compared1[0]);
// Print the second largest element
System.out.print(compared2[1]);
}
// Driver code
public static void main(String[] args)
{
int N = 10;
int []arr ={20, 1990, 12, 1110, 1,
59, 12, 15, 120, 1110};
findSecondLargest(N, arr);
}
}
// This code is contributed by gauravrajput1
Python3
# Python3 Program to implement # the above approach # Function to find the largest # element in the array arr[] def findLargest(beg, end, arr, n): # Base Condition if(beg == end): # Initialize an empty list compared = [0]*n compared[0] = 1 compared[1] = arr[beg] return compared # Divide the array into two equal # length subarrays and recursively # find the largest among the two compared1 = findLargest(beg, (beg+end)//2, arr, n) compared2 = findLargest((beg+end)//2+1, end, arr, n) if(compared1[1] > compared2[1]): k = compared1[0]+1 # Store length of compared1[] # in the first index compared1[0] = k # Store the maximum element compared1[k] = compared2[1] # Return compared1 which # contains the maximum element return compared1 else: k = compared2[0]+1 # Store length of compared2[] # in the first index compared2[0] = k # Store the maximum element compared2[k] = compared1[1] # Return compared2[] which # contains the maximum element return compared2 # Function to print the second largest # element in the array arr[] def findSecondLargest(end, arr): # Find the largest element in arr[] compared1 = findLargest(0, end-1, arr, end) # Find the second largest element # in arr[] compared2 = findLargest(2, compared1[0]+2, compared1, compared1[0]) # Print the second largest element print(compared2[1]) # Driver Code N = 10 arr = [20, 1990, 12, 1110, 1, 59, 12, 15, 120, 1110] findSecondLargest(N, arr)
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function to find the largest
// element in the array arr[]
static int[] findLargest(int beg, int end,
int []arr, int n)
{
// Base Condition
if (beg == end)
{
// Initialize an empty list
int []compared = new int[n];
compared[0] = 1;
compared[1] = arr[beg];
return compared;
}
// Divide the array into two equal
// length subarrays and recursively
// find the largest among the two
int []compared1 = findLargest(beg,
(beg + end) /
2, arr, n);
int []compared2 = findLargest((beg + end) /
2 + 1,
end, arr, n);
if (compared1[1] > compared2[1])
{
int k = compared1[0] + 1;
// Store length of compared1[]
// in the first index
compared1[0] = k;
// Store the maximum element
compared1[k] = compared2[1];
// Return compared1 which
// contains the maximum element
return compared1;
}
else
{
int k = compared2[0] + 1;
// Store length of compared2[]
// in the first index
compared2[0] = k;
// Store the maximum element
compared2[k] = compared1[1];
// Return compared2[] which
// contains the maximum element
return compared2;
}
}
// Function to print the second largest
// element in the array arr[]
static void findSecondLargest(int end,
int []arr)
{
// Find the largest element in arr[]
int []compared1 = findLargest(0, end - 1,
arr, end);
// Find the second largest element
// in arr[]
int []compared2 = findLargest(2, compared1[0] + 2,
compared1,
compared1[0]);
// Print the second largest element
Console.WriteLine(compared2[1]);
}
// Driver code
static public void Main ()
{
int N = 10;
int []arr = { 20, 1990, 12, 1110, 1,
59, 12, 15, 120, 1110 };
findSecondLargest(N, arr);
}
}
// This code is contributed by offbeat
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the largest
// element in the array arr[]
function findLargest(beg,end,arr,n)
{
// Base Condition
if (beg == end)
{
// Initialize an empty list
let compared = new Array(n);
for(let i=0;i<n;i++)
compared[i]=0;
compared[0] = 1;
compared[1] = arr[beg];
return compared;
}
// Divide the array into two equal
// length subarrays and recursively
// find the largest among the two
let compared1 = findLargest(beg,
Math.floor((beg + end) /
2), arr, n);
let compared2 = findLargest(Math.floor((beg + end) /
2 )+ 1,
end, arr, n);
if (compared1[1] > compared2[1])
{
let k = compared1[0] + 1;
// Store length of compared1[]
// in the first index
compared1[0] = k;
// Store the maximum element
compared1[k] = compared2[1];
// Return compared1 which
// contains the maximum element
return compared1;
}
else
{
let k = compared2[0] + 1;
// Store length of compared2[]
// in the first index
compared2[0] = k;
// Store the maximum element
compared2[k] = compared1[1];
// Return compared2[] which
// contains the maximum element
return compared2;
}
}
// Function to print the second largest
// element in the array arr[]
function findSecondLargest(end,arr)
{
// Find the largest element in arr[]
let compared1 = findLargest(0, end - 1,
arr, end);
// Find the second largest element
// in arr[]
let compared2 = findLargest(2, compared1[0] + 2,
compared1,
compared1[0]);
// Print the second largest element
document.write(compared2[1]);
}
// Driver code
let N = 10;
let arr=[20, 1990, 12, 1110, 1,
59, 12, 15, 120, 1110];
findSecondLargest(N, arr);
// This code is contributed by unknown2108
</script>
Producción:
1110
Complejidad temporal: O(N)
Espacio auxiliar: O(logN)
Publicación traducida automáticamente
Artículo escrito por shawavisek35 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA