Dada una array nxn y un entero k. Encuentre el k-ésimo elemento más pequeño en la array 2D dada. Ejemplos:
Input : mat = [[10, 25, 20, 40],
[15, 45, 35, 30],
[24, 29, 37, 48],
[32, 33, 39, 50]]
k = 7
Output : 7th smallest element is 30
Usaremos un enfoque similar como K’th Smallest/Largest Element en Unsorted Array para resolver este problema.
- Cree un montón mínimo vacío usando heapq en python.
- Ahora asigne la primera fila (lista) en la variable de resultado y convierta la lista de resultados en un montón mínimo usando el método heapify .
- Ahora recorra los elementos de fila restantes y empújelos al montón mínimo creado.
- Ahora obtenga el k-ésimo elemento más pequeño usando el método nsmallest(k, iterable) del módulo heapq.
Implementación:
Python3
# Function to find K'th smallest element in # a 2D array in Python import heapq def kthSmallest(input): # assign first row to result variable # and convert it into min heap result = input[0] heapq.heapify(result) # now traverse remaining rows and push # elements in min heap for row in input[1:]: for ele in row: heapq.heappush(result,ele) # get list of first k smallest element because # nsmallest(k,list) method returns first k # smallest element now print last element of # that list kSmallest = heapq.nsmallest(k,result) print (k,"th smallest element is ",kSmallest[-1]) # Driver program if __name__ == "__main__": input = [[10, 25, 20, 40], [15, 45, 35, 30], [24, 29, 37, 48], [32, 33, 39, 50]] k = 7 kthSmallest(input)
Producción
7 th smallest element is 30
Publicación traducida automáticamente
Artículo escrito por Shashank Mishra y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA