Найдите 10 строк наибольшего количества в текстовом файле с идентификатором отгрузки, кодом UPC, количеством

Question

Это вопрос интервью.

Для каждого текстового файла каждая строка содержит: идентификатор отгрузки, код UPC, количество

Найдите 10 строк наибольшего количества.

Мои решения:

С помощью c ++

создать минимальную кучу (с размером 10) с количеством в качестве объекта сравнения.

Читать каждую запись как структурус полем {идентификатор отгрузки, код UPC, количество}

Сравните его с верхним элементом 10-элементной минимальной кучи,

, если> замените верхний элемент на него, иначе прочитайтеследующий элемент.

Это O (n lg n).

Пробел O (1).

Лучшие решения?

спасибо

Answer 1

Примечание: ваши затраты времени на самом деле O (n), поскольку время вставки для каждого элемента является постоянным (O (log 10)).

Основная идея - это звук - вы не будетесделать лучше, чем O (n) с точки зрения стоимости - но вместо того, чтобы свернуть собственную кучу, используйте std::priority_queue.