Dada una array con todos los elementos distintos, encuentre los tres elementos más grandes. La complejidad de tiempo esperada es O(n) y el espacio extra es O(1).
Ejemplos:
Input: arr[] = {10, 4, 3, 50, 23, 90}
Output: 90, 50, 23
Método 1:
Algoritmo:
1) Initialize the largest three elements as minus infinite.
first = second = third = -∞
2) Iterate through all elements of array.
a) Let current array element be x.
b) If (x > first)
{
// This order of assignment is important
third = second
second = first
first = x
}
c) Else if (x > second and x != first)
{
third = second
second = x
}
d) Else if (x > third and x != second)
{
third = x
}
3) Print first, second and third.
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program for find the largest
// three elements in an array
#include <bits/stdc++.h>
using namespace std;
// Function to print three largest elements
void print3largest(int arr[], int arr_size)
{
int first, second, third;
// There should be atleast three elements
if (arr_size < 3)
{
cout << " Invalid Input ";
return;
}
third = first = second = INT_MIN;
for(int i = 0; i < arr_size; i++)
{
// If current element is
// greater than first
if (arr[i] > first)
{
third = second;
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)
{
third = second;
second = arr[i];
}
else if (arr[i] > third && arr[i] != second)
third = arr[i];
}
cout << "Three largest elements are "
<< first << " " << second << " "
<< third << endl;
}
// Driver code
int main()
{
int arr[] = { 12, 13, 1, 10, 34, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
print3largest(arr, n);
return 0;
}
// This code is contributed by Anjali_Chauhan
C
// C program for find the largest
// three elements in an array
#include <limits.h> /* For INT_MIN */
#include <stdio.h>
/* Function to print three largest elements */
void print3largest(int arr[], int arr_size)
{
int i, first, second, third;
/* There should be atleast three elements */
if (arr_size < 3) {
printf(" Invalid Input ");
return;
}
third = first = second = INT_MIN;
for (i = 0; i < arr_size; i++) {
/* If current element is greater than first*/
if (arr[i] > first) {
third = second;
second = first;
first = arr[i];
}
/* If arr[i] is in between first and second then update second */
else if (arr[i] > second) {
third = second;
second = arr[i];
}
else if (arr[i] > third)
third = arr[i];
}
printf("Three largest elements are %d %d %d\n", first, second, third);
}
/* Driver program to test above function */
int main()
{
int arr[] = { 12, 13, 1, 10, 34, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
print3largest(arr, n);
return 0;
}
/*This code is edited by Ayush Singla(@ayusin51)*/
Java
// Java code to find largest three elements
// in an array
class PrintLargest {
/* Function to print three largest elements */
static void print3largest(int arr[], int arr_size)
{
int i, first, second, third;
/* There should be atleast three elements */
if (arr_size < 3) {
System.out.print(" Invalid Input ");
return;
}
third = first = second = Integer.MIN_VALUE;
for (i = 0; i < arr_size; i++) {
/* If current element is greater than
first*/
if (arr[i] > first) {
third = second;
second = first;
first = arr[i];
}
/* If arr[i] is in between first and
second then update second */
else if (arr[i] > second) {
third = second;
second = arr[i];
}
else if (arr[i] > third)
third = arr[i];
}
System.out.println("Three largest elements are " + first + " " + second + " " + third);
}
/* Driver program to test above function*/
public static void main(String[] args)
{
int arr[] = { 12, 13, 1, 10, 34, 1 };
int n = arr.length;
print3largest(arr, n);
}
}
/*This code is contributed by Prakriti Gupta
and edited by Ayush Singla(@ayusin51)*/
Python3
# Python3 code to find largest three
# elements in an array
import sys
# Function to print three largest
# elements
def print3largest(arr, arr_size):
# There should be atleast three
# elements
if (arr_size < 3):
print(" Invalid Input ")
return
third = first = second = -sys.maxsize
for i in range(0, arr_size):
# If current element is greater
# than first
if (arr[i] > first):
third = second
second = first
first = arr[i]
# If arr[i] is in between first
# and second then update second
elif (arr[i] > second):
third = second
second = arr[i]
elif (arr[i] > third):
third = arr[i]
print("Three largest elements are",
first, second, third)
# Driver program to test above function
arr = [12, 13, 1, 10, 34, 1]
n = len(arr)
print3largest(arr, n)
# This code is contributed by Smitha Dinesh Semwal
# and edited by Ayush Singla(@ayusin51).
C#
// C# code to find largest
// three elements in an array
using System;
class PrintLargest {
// Function to print three
// largest elements
static void print3largest(int[] arr,
int arr_size)
{
int i, first, second, third;
// There should be atleast three elements
if (arr_size < 3) {
Console.WriteLine("Invalid Input");
return;
}
third = first = second = 000;
for (i = 0; i < arr_size; i++) {
// If current element is
// greater than first
if (arr[i] > first) {
third = second;
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) {
third = second;
second = arr[i];
}
else if (arr[i] > third && arr[i]!=second)
third = arr[i];
}
Console.WriteLine("Three largest elements are " + first + " " + second + " " + third);
}
// Driver code
public static void Main()
{
int[] arr = new int[] { 12, 13, 1, 10, 34, 1 };
int n = arr.Length;
print3largest(arr, n);
}
}
// This code is contributed by KRV and edited by Ayush Singla(@ayusin51).
PHP
<?php
// PHP code to find largest
// three elements in an array
// Function to print
// three largest elements
function print3largest($arr, $arr_size)
{
$i; $first; $second; $third;
// There should be atleast
// three elements
if ($arr_size < 3)
{
echo " Invalid Input ";
return;
}
$third = $first = $second = PHP_INT_MIN;
for ($i = 0; $i < $arr_size ; $i ++)
{
// If current element is
// greater than first
if ($arr[$i] > $first)
{
$third = $second;
$second = $first;
$first = $arr[$i];
}
// If arr[i] is in between first
// and second then update second
else if ($arr[$i] > $second)
{
$third = $second;
$second = $arr[$i];
}
else if ($arr[$i] > $third)
$third = $arr[$i];
}
echo "Three largest elements are ",
$first, " ", $second, " ", $third;
}
// Driver Code
$arr = array(12, 13, 1,
10, 34, 1);
$n = count($arr);
print3largest($arr, $n);
// This code is contributed by anuj_67 and edited by Ayush Singla(@ayusin51).
?>
Javascript
<script>
// Javascript program for find the largest
// three elements in an array
// Function to print three largest elements
function print3largest(arr, arr_size)
{
let first, second, third;
// There should be atleast three elements
if (arr_size < 3)
{
document.write(" Invalid Input ");
return;
}
third = first = second = Number.MIN_VALUE;
for(let i = 0; i < arr_size; i++)
{
// If current element is
// greater than first
if (arr[i] > first)
{
third = second;
second = first;
first = arr[i];
}
// If arr[i] is in between first
// and second then update second
else if (arr[i] > second)
{
third = second;
second = arr[i];
}
else if (arr[i] > third)
third = arr[i];
}
document.write("Three largest elements are "
+ first + " " + second + " "
+ third + "<br>");
}
// Driver code
let arr = [ 12, 13, 1, 10, 34, 1 ];
let n = arr.length;
print3largest(arr, n);
// This is code is contributed by Mayank Tyagi
</script>
Producción
Three largest elements are 34 13 12
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Método 2:
Una forma eficiente de resolver este problema es usar cualquier algoritmo de clasificación O(nLogn) y simplemente devolver los últimos 3 elementos más grandes.
C++
// C++ code to find largest three elements in an array
#include <bits/stdc++.h>
using namespace std;
void find3largest(int arr[], int n)
{
sort(arr, arr + n); // It uses Tuned Quicksort with
// avg. case Time complexity = O(nLogn)
int check = 0, count = 1;
for (int i = 1; i <= n; i++) {
if (count < 4) {
if (check != arr[n - i]) {
// to handle duplicate values
cout << arr[n - i] << " ";
check = arr[n - i];
count++;
}
}
else
break;
}
}
// Driver code
int main()
{
int arr[] = { 12, 45, 1, -1, 45, 54, 23, 5, 0, -10 };
int n = sizeof(arr) / sizeof(arr[0]);
find3largest(arr, n);
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C code to find largest three elements in an array
#include <stdio.h>
#include <stdlib.h>
// Compare function for qsort
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
void find3largest(int arr[], int n)
{
qsort(arr, n, sizeof(int),
cmpfunc); // It uses Tuned Quicksort with
// avg. case Time complexity = O(nLogn)
int check = 0, count = 1;
for (int i = 1; i <= n; i++) {
if (count < 4) {
if (check != arr[n - i]) {
// to handle duplicate values
printf("%d ", arr[n - i]);
check = arr[n - i];
count++;
}
}
else
break;
}
}
// Driver code
int main()
{
int arr[] = { 12, 45, 1, -1, 45, 54, 23, 5, 0, -10 };
int n = sizeof(arr) / sizeof(arr[0]);
find3largest(arr, n);
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java code to find largest
// three elements in an array
import java.io.*;
import java.util.Arrays;
class GFG {
void find3largest(int[] arr)
{
Arrays.sort(arr); // It uses Tuned Quicksort with
// avg. case Time complexity = O(nLogn)
int n = arr.length;
int check = 0, count = 1;
for (int i = 1; i <= n; i++) {
if (count < 4) {
if (check != arr[n - i]) {
// to handle duplicate values
System.out.print(arr[n - i] + " ");
check = arr[n - i];
count++;
}
}
else
break;
}
}
// Driver code
public static void main(String[] args)
{
GFG obj = new GFG();
int[] arr = { 12, 45, 1, -1, 45, 54, 23, 5, 0, -10 };
obj.find3largest(arr);
}
}
// This code is contributed by Prashant Malik
Python3
# Python3 code to find largest # three elements in an array def find3largest(arr, n): arr = sorted(arr) # It uses Tuned Quicksort with # avg. case Time complexity = O(nLogn) check = 0 count = 1 for i in range(1, n + 1): if(count < 4): if(check != arr[n - i]): # to handle duplicate values print(arr[n - i], end = " ") check = arr[n - i] count += 1 else: break # Driver code arr = [12, 45, 1, -1, 45, 54, 23, 5, 0, -10] n = len(arr) find3largest(arr, n) # This code is contributed by mohit kumar
C#
// C# code to find largest
// three elements in an array
using System;
class GFG {
void find3largest(int[] arr)
{
Array.Sort(arr); // It uses Tuned Quicksort with
// avg. case Time complexity = O(nLogn)
int n = arr.Length;
int check = 0, count = 1;
for (int i = 1; i <= n; i++) {
if (count < 4) {
if (check != arr[n - i]) {
// to handle duplicate values
Console.Write(arr[n - i] + " ");
check = arr[n - i];
count++;
}
}
else
break;
}
}
// Driver code
public static void Main()
{
GFG obj = new GFG();
int[] arr = { 12, 45, 1, -1, 45,
54, 23, 5, 0, -10 };
obj.find3largest(arr);
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// JavaScript code to find largest
// three elements in an array
function find3largest(arr) {
arr.sort((a,b)=>a-b); // It uses Tuned Quicksort with
// avg. case Time complexity = O(nLogn)
let check = 0, count = 1;
for (let i = 1; i <= arr.length; i++) {
if (count < 4) {
if (check != arr[arr.length - i]) {
// to handle duplicate values
document.write(arr[arr.length - i] + " ");
check = arr[arr.length - i];
count++;
}
}
else
break;
}
}
// Driver code
let arr = [ 12, 45, 1, -1, 45, 54, 23, 5, 0, -10 ];
find3largest(arr);
// This code is contributed by Surbhi Tyagi
</script>
Producción
54 45 23
Complejidad de Tiempo: O(n log n)
Espacio Auxiliar: O(1)
Método 3:
podemos usar la ordenación parcial de C++ STL. Partial_sort usa Heapselect, que proporciona un mejor rendimiento que Quickselect para M pequeños. Como efecto secundario, el estado final de Heapselect te deja con un montón, lo que significa que obtienes la primera mitad del algoritmo Heapsort «gratis». La complejidad es «aproximadamente» O(N log(M)) , donde M es la distancia (en medio primero).
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
vector<int> V = { 11, 65, 193, 36, 209, 664, 32 };
partial_sort(V.begin(), V.begin() + 3, V.end(), greater<int>());
cout << "first = " << V[0] << "\n";
cout << "second = " << V[1] << "\n";
cout << "third = " << V[2] << "\n";
return 0;
}
Java
// java program to find
// three largest elements
// in array.
import java.io.*;
import java.util.Arrays;
class GFG{
public static void main(String[] args)
{
int[] V = { 11, 65, 193, 36, 209, 664, 32 };
// sorting the array
Arrays.sort(V);
// taking the length of array
int x = V.length;
System.out.println("first = " + V[x-1] );
System.out.println("second = " + V[x-2]);
System.out.println("third = " + V[x-3] );
}
}
// This code is Contributed Machhaliya Muhammad
Python3
# Python program to implement
# the above approach
# Driver Code
V = [ 11, 65, 193, 36, 209, 664, 32 ];
V.sort()
V.reverse()
print(f"first = {V[0]}");
print(f"second = {V[1]}");
print(f"third = {V[2]}");
# This code is contributed by Saurabh Jaiswal
C#
// C# program to implement
// the above approach
using System;
class GFG
{
// Driver Code
public static void Main()
{
int[] V = { 11, 65, 193, 36, 209, 664, 32 };
Array.Sort(V);
Array.Reverse(V);
Console.WriteLine("first = " + V[0] );
Console.WriteLine("second = " + V[1]);
Console.WriteLine("third = " + V[2] );
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// Javascript program to implement
// the above approach
// Driver Code
let V = [ 11, 65, 193, 36, 209, 664, 32 ];
V.sort((a, b) => a - b)
V.reverse()
document.write("first = " + V[0] + "<br>");
document.write("second = " + V[1] + "<br>");
document.write("third = " + V[2] + "<br>");
// This code is contributed by Saurabh Jaiswal
</script>
Producción
first = 664 second = 209 third = 193
Complejidad de tiempo: O (n log m) donde m es la distancia (medio-primero).
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA