Dada una array arr[] y un entero k, necesitamos imprimir k elementos máximos de la array dada. Los elementos deben imprimirse en el orden de la entrada.
Nota: k siempre es menor o igual que n.
Ejemplos:
Input : arr[] = {10 50 30 60 15}
k = 2
Output : 50 60
The top 2 elements are printed
as per their appearance in original
array.
Input : arr[] = {50 8 45 12 25 40 84}
k = 3
Output : 50 45 84
Método 1: Buscamos el elemento máximo k veces en la array dada. Cada vez que encontramos un elemento máximo, lo imprimimos y lo reemplazamos con menos infinito (INT_MIN en C) en la array. Además, la posición de todos los k elementos máximos se marca mediante una array para que con la ayuda de esa array podamos imprimir los elementos en el orden dado en la array original. La complejidad temporal de este método es O(n*k).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find k maximum elements
// of array in original order
#include <bits/stdc++.h>
using namespace std;
// Function to print k Maximum elements
void printMax(int arr[], int k, int n)
{
int brr[n]={0},crr[n];
// Coping the array arr
// into crr so that it
// can be used later
for(int i=0;i<n;i++)
{
crr[i]=arr[i];
}
// Iterating for K-times
for(int i=0;i<k;i++)
{
// Finding the maximum element
// along with its index
int maxi=INT_MIN;
int index;
for(int j=0;j<n;j++)
{
if(maxi<arr[j])
{
maxi=arr[j];
index=j;
}
}
// Assigning 1 in order
// to mark the position
// of all k maximum numbers
brr[index]=1;
arr[index]=INT_MIN;
}
for(int i=0;i<n;i++)
{
// Printing the k maximum
// elements array
if(brr[i]==1)
cout<<crr[i]<<" ";
}
}
// Driver code
int main()
{
int arr[] = { 50, 8, 45, 12, 25, 40, 84 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
printMax(arr, k, n);
return 0;
}
// This code is contributed by Pushpesh Raj.
Java
// JAVA program to find k maximum elements
// of array in original order
import java.util.*;
class GFG {
// Function to print k Maximum elements
public static void printMax(int arr[], int k, int n)
{
int brr[] = new int[n];
int crr[] = new int[n];
for (int i = 0; i < n; i++)
brr[i] = 0;
// Coping the array arr
// into crr so that it
// can be used later
for (int i = 0; i < n; i++) {
crr[i] = arr[i];
}
// Iterating for K-times
for (int i = 0; i < k; i++)
{
// Finding the maximum element
// along with its index
int maxi = Integer.MIN_VALUE;
int index = 0;
for (int j = 0; j < n; j++) {
if (maxi < arr[j]) {
maxi = arr[j];
index = j;
}
}
// Assigning 1 in order
// to mark the position
// of all k maximum numbers
brr[index] = 1;
arr[index] = Integer.MIN_VALUE;
}
for (int i = 0; i < n; i++)
{
// Printing the k maximum
// elements array
if (brr[i] == 1)
System.out.print(crr[i] + " ");
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = new int[] { 50, 8, 45, 12, 25, 40, 84 };
int n = arr.length;
int k = 3;
printMax(arr, k, n);
}
}
// This code is contributed by Taranpreet
Python3
# Function to print k Maximum elements
def printMax(arr, k, n):
brr = [0 for _ in range(n)]
crr = [0 for _ in range(n)]
# Coping the array arr
# into crr so that it
# can be used later
for i in range(0, n):
crr[i] = arr[i]
# Iterating for K-times
for i in range(0, k):
# Finding the maximum element
# along with its index
maxi = -99999
index = 0
for j in range(0, n):
if maxi < arr[j]:
maxi = arr[j]
index = j
# Assigning 1 in order
# to mark the position
# of all k maximum numbers
brr[index] = 1
arr[index] = -99999
for i in range(0, n):
# Printing the k maximum
# elements array
if brr[i] == 1:
print(crr[i], end='')
print(" ", end='')
if __name__ == "__main__":
arr = [50, 8, 45, 12, 25, 40, 84]
n = len(arr)
k = 3
printMax(arr, k, n)
# This code is contributed by Aarti_Rathi
C#
// C# program to find k maximum
// elements of array in original order
using System;
using System.Linq;
class GFG {
// Function to print m Maximum elements
public static void printMax(int[] arr, int k, int n)
{
// Coping the array arr
// into crr so that it
// can be used later
int[] brr = new int[n];
int[] crr = new int[n];
for (int i = 0; i < n; i++) {
brr[i] = 0;
crr[i] = arr[i];
}
// Iterating for K-times
for (int i = 0; i < k; i++) {
// Finding the maximum element
// along with its index
int maxi = Int32.MinValue;
int index = 0;
for (int j = 0; j < n; j++) {
if (maxi < arr[j]) {
maxi = arr[j];
index = j;
}
}
// Assigning 1 in order
// to mark the position
// of all k maximum numbers
brr[index] = 1;
arr[index] = Int32.MinValue;
}
for (int i = 0; i < n; i++) {
// Printing the k maximum
// elements array
if (brr[i] == 1)
Console.Write(crr[i] + " ");
}
}
// Driver code
public static void Main()
{
int[] arr = { 50, 8, 45, 12, 25, 40, 84 };
int n = arr.Length;
int k = 3;
printMax(arr, k, n);
}
}
// This code is contributed by Aarti_Rathi
Javascript
// Function to print k Maximum elements
function printMax(arr, k, n)
{
var brr = Array(n).fill(0);
var crr = Array(n).fill(0);
for (var i =0; i < n; i++)
{
brr[i] = 0;
}
// Coping the array arr
// into crr so that it
// can be used later
for (var i=0; i < n; i++)
{
crr[i] = arr[i];
}
// Iterating for K-times
for (var i=0; i < k; i++)
{
// Finding the maximum element
// along with its index
var maxi = -Number.MAX_VALUE;
var index = 0;
for (var j =0; j < n; j++)
{
if (maxi < arr[j])
{
maxi = arr[j];
index = j;
}
}
// Assigning 1 in order
// to mark the position
// of all k maximum numbers
brr[index] = 1;
arr[index] = -Number.MAX_VALUE;
}
for (var i=0; i < n; i++)
{
// Printing the k maximum
// elements array
if (brr[i] == 1)
{
console.log(crr[i] + " ");
}
}
}
// Driver code
var arr = [50, 8, 45, 12, 25, 40, 84];
var n = arr.length;
var k = 3;
printMax(arr, k, n);
// This code is contributed by Aarti_Rathi
Producción
50 45 84
Complejidad temporal: O(n*k)
Espacio auxiliar: O(n)
Método 2: en este método, almacenamos la array original en una nueva array y ordenaremos la nueva array en orden descendente. Después de ordenar, iteramos la array original de 0 a n e imprimimos todos los elementos que aparecen en los primeros k elementos de la nueva array. Para buscar, podemos hacer Búsqueda binaria .
C++
// C++ program to find k maximum elements
// of array in original order
#include <bits/stdc++.h>
using namespace std;
// Function to print m Maximum elements
void printMax(int arr[], int k, int n)
{
// vector to store the copy of the
// original array
vector<int> brr(arr, arr + n);
// Sorting the vector in descending
// order. Please refer below link for
// details
// https://www.geeksforgeeks.org/sort-c-stl/
sort(brr.begin(), brr.end(), greater<int>());
// Traversing through original array and
// printing all those elements that are
// in first k of sorted vector.
// Please refer https://goo.gl/44Rwgt
// for details of binary_search()
for (int i = 0; i < n; ++i)
if (binary_search(brr.begin(),
brr.begin() + k, arr[i],
greater<int>()))
cout << arr[i] << " ";
}
// Driver code
int main()
{
int arr[] = { 50, 8, 45, 12, 25, 40, 84 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
printMax(arr, k, n);
return 0;
}
Java
// Java program to find k maximum
// elements of array in original order
import java.util.Arrays;
import java.util.Collections;
public class GfG {
// Function to print m Maximum elements
public static void printMax(int arr[], int k, int n)
{
// Array to store the copy
// of the original array
Integer[] brr = new Integer[n];
for (int i = 0; i < n; i++)
brr[i] = arr[i];
// Sorting the array in
// descending order
Arrays.sort(brr, Collections.reverseOrder());
// Traversing through original array and
// printing all those elements that are
// in first k of sorted array.
// Please refer https://goo.gl/uj5RCD
// for details of Arrays.binarySearch()
for (int i = 0; i < n; ++i)
if (Arrays.binarySearch(brr, arr[i],
Collections.reverseOrder()) >= 0
&& Arrays.binarySearch(brr, arr[i],
Collections.reverseOrder()) < k)
System.out.print(arr[i]+ " ");
}
// Driver code
public static void main(String args[])
{
int arr[] = { 50, 8, 45, 12, 25, 40, 84 };
int n = arr.length;
int k = 3;
printMax(arr, k, n);
}
}
// This code is contributed by Swetank Modi
Python3
# Python3 program to find k maximum elements # of array in original order # Function to print m Maximum elements def printMax(arr, k, n): # vector to store the copy of the # original array brr = arr.copy() # Sorting the vector in descending # order. Please refer below link for # details brr.sort(reverse = True) # Traversing through original array and # print all those elements that are # in first k of sorted vector. for i in range(n): if (arr[i] in brr[0:k]): print(arr[i], end = " ") # Driver code arr = [ 50, 8, 45, 12, 25, 40, 84 ] n = len(arr) k = 3 printMax(arr, k, n) # This code is contributed by SHUBHAMSINGH10
C#
// C# program to find k maximum
// elements of array in original order
using System;
using System.Linq;
class GFG{
// Function to print m Maximum elements
public static void printMax(int[] arr, int k,
int n)
{
// Array to store the copy
// of the original array
int[] brr = new int[n];
for(int i = 0; i < n; i++)
brr[i] = arr[i];
// Sorting the array in
// descending order
Array.Sort(brr);
Array.Reverse(brr);
int[] crr = new int[k];
for(int i = 0; i < k; i++)
{
crr[i] = brr[i];
}
// Traversing through original array and
// printing all those elements that are
// in first k of sorted array.
// Please refer https://goo.gl/uj5RCD
// for details of Array.BinarySearch()
for(int i = 0; i < n; ++i)
{
if (crr.Contains(arr[i]))
{
Console.Write(arr[i] + " ");
}
}
}
// Driver code
public static void Main()
{
int[] arr = { 50, 8, 45, 12, 25, 40, 84 };
int n = arr.Length;
int k = 3;
printMax(arr, k, n);
}
}
// This code is contributed by Shubhamsingh10
Javascript
<script>
// JavaScript program to find k maximum elements
// of array in original order
// Function to print m Maximum elements
function printMax(arr, k, n)
{
// vector to store the copy of the
// original array
var brr = arr.slice();
// Sorting the vector in descending
// order. Please refer below link for
// details
// https://www.geeksforgeeks.org/sort-c-stl/
brr.sort((a, b) => b - a);
// Traversing through original array and
// printing all those elements that are
// in first k of sorted vector.
// Please refer https://goo.gl/44Rwgt
// for details of binary_search()
for (var i = 0; i < n; ++i)
if (brr.indexOf(arr[i]) < k)
document.write(arr[i] +" ");
}
// Driver code
var arr = [ 50, 8, 45, 12, 25, 40, 84 ];
var n = arr.length;
var k = 3;
printMax(arr, k, n);
// This code is contributed by ShubhamSingh10
</script>
Producción
50 45 84
Complejidad de tiempo: O(n Log n) para ordenar.
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por agrawalmohak99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA