#algorithm #string #file #long-integer #lines
#алгоритм #строка #файл #длинное целое число #строки
Вопрос:
Первая строка содержит значение числа ‘N’, за которым следует несколько строк. Я мог бы решить это в порядке алгоритма n ^ 2. Кто-нибудь может предложить лучший вариант?
Ответ №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. -
это также можно было бы сделать в O (n) с помощью Select (N) (который выбирает N-е число), за которым следует разбиение вокруг N-го числа (которое упорядочивает все с размером, большим или равным N-му числу, с одной стороны от него).
i = Select(lines, N) partition(lines, i) for i to size(lines): print to stdout: lines[i]
Комментарии:
1. Это не тривиальный алгоритм, скажем, типа partition … более подробную информацию можно найти здесь: en.wikipedia.org/wiki/Select_algorithm
2. куча упорядочена по длине строки. итак, как вы вставляете строку в кучу. я имею в виду, как у вас есть соответствие между строкой и ее длиной? вы используете структуру или что-то в этомроде?
3. Ну, этот вопрос не зависит от языка… но, вообще говоря, элементы, которые, как ожидается, будут вставлены в кучу, могут сравниваться друг с другом. Поскольку вы спрашиваете о структурах, я предполагаю, что вы используете C, поэтому при вставке новых элементов вы бы упорядочивали их с помощью strlen() . (Я думаю, вы могли бы использовать структуру с полем для длины строки и сохранить вызов strlen(), если хотите некоторой оптимизации).