Programa de Python 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 (-1*sys.maxsize para el valor mínimo más grande en Python) 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). 

# Python program to find k maximum elements
# of array in original order
 
# import the module
import sys
 
# Function to print k Maximum elements
def printMax(arr, k, n):
    brr=[0]*n
    crr=[0]*n
     
    # Coping the array arr
    # into crr so that it
    # can be used later
    for i in range(n):
        crr[i]=arr[i]
         
    # Iterating for K-times
    for i in range(k):
        # Finding the maximum element
        # along with its index
        maxi=-1*sys.maxsize
        for j in range(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]=-1*sys.maxsize
         
    for i in range(n):
        # Printing the k maximum
        # elements array
        if(brr[i]==1):
            print(crr[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 Pushpesh Raj.

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 .

# Python3 program to find k maximum elements
# of array in original order
 
# Function to print  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

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.