¿Cómo encontrar N líneas más largas en un archivo de texto e imprimirlas en stdout?

Question

La primera línea contiene el valor del número 'N' seguido de varias líneas. Podría resolverlo en orden de algoritmo n^2. ¿Alguien puede sugerir uno mejor?

Answer 1

1. Puede utilizar un mínimo-montón y hacerlo en O (n * (log (N))):

   heap = new Min-Heap(N) 
       foreach line in text: 
        if length(line) > heap.min(): 
        heap.pop() 
        heap.insert(line) 
       foreach line in heap: 
        print to stdout: line. 
   

2. también podría hacerse en O (n) usando Select (N) (que selecciona el N-ésimo número) seguido de una partición alrededor del N-ésimo número (que ordena todos los que tienen un tamaño mayor o igual al N-ésimo número de un lado).

   i = Select(lines, N) 
       partition(lines, i) 
       for i to size(lines): 
        print to stdout: lines[i]