Programa Java para encontrar k elementos máximos de array en el orden original

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 (Integer.MIN_VALUE en Java) 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).

// Java program to find k maximum elements
// of array in original order
 
import java.util.*;
import java.util.Arrays;
import java.util.Collections;
 
class GFG
{
 // Function to print k Maximum elements
public static void printMax(int arr[], int k, int n)
{
    int[] brr = new int[n];
    Arrays.fill(brr, 0);
    int[] crr = new int[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=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 = { 50, 8, 45, 12, 25, 40, 84 };
    int n = arr.length;
    int k = 3;
    printMax(arr, k, 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 .

// 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

50 45 84 

Complejidad de tiempo: O(n Log n) para ordenar. 
Espacio Auxiliar: O(n)
 

¡ Consulte el artículo completo sobre Encontrar k elementos máximos de array en el orden original para obtener más detalles!