Как найти N длинных строк в текстовом файле и распечатать их на стандартный вывод?

Question

Первая строка содержит значение числа 'N', за которым следуют несколько строк. Я мог бы решить это в порядке n ^ 2 алгоритма. Кто-нибудь может предложить лучший вариант?

Answer 1

1. Вы можете использовать минимальную кучу и сделать это в 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. это также можетсделать в O (n), используя Select (N) (который выбирает N-е число) с последующим разделением вокруг N-го числа (который размещает все с размером, большим или равным N-му числу с одной стороны от него).

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