Вот одно из возможных решений, которое работает с использованием множества связанных списков.
Основная идея c заключается в следующем. Для каждого расположения массива создайте двусвязную ячейку списка, представляющую этот элемент массива. Затем сгруппируйте все элементы в массиве по их значению цифра c. Например, когда вы впервые создаете массив и все имеет нулевое значение, у вас будет двусвязный список всех положений массива, например:
+---+ +---+ +---+ +---+ +---+
| 0 | <-> | 1 | <-> | 2 | <-> | 3 | <-> | 4 |
+---+ +---+ +---+ +---+ +---+
Всякий раз, когда вы увеличиваете значение на единицу, склеить его из списка, в котором он находится, и добавить его в новый список, представляющий значения, которые на единицу больше, чем предыдущее значение. Например, при увеличении индекса массива 3 все будет выглядеть следующим образом:
+---+ +---+ +---+ +---+
Cells with value 0 | 0 | <-> | 1 | <-> | 2 | <-> | 4 |
+---+ +---+ +---+ +---+
+---+
Cells with value 1 | 3 |
+---+
При увеличении ячейки 2 это будет выглядеть так:
+---+ +---+ +---+
Cells with value 0 | 0 | <-> | 1 | <-> | 4 |
+---+ +---+ +---+
+---+ +---+
Cells with value 1 | 2 | <-> | 3 |
+---+ +---+
При увеличении ячейки 3 снова получится следующее:
+---+ +---+ +---+
Cells with value 0 | 0 | <-> | 1 | <-> | 4 |
+---+ +---+ +---+
+---+
Cells with value 1 | 2 |
+---+
+---+
Cells with value 2 | 3 |
+---+
Теперь предположим, что вы снова увеличили ячейку (2). Это переместит ячейку (2) в связанный список для ячеек со значением 2. Поскольку список ячеек со значением (1) больше не нужен, мы можем просто удалить его:
+---+ +---+ +---+
Cells with value 0 | 0 | <-> | 1 | <-> | 4 |
+---+ +---+ +---+
+---+ +---+
Cells with value 2 | 2 | <-> | 3 |
+---+ +---+
Чтобы увеличить 0 Затем мы воссоздаем список со значением 1, как показано здесь:
+---+ +---+
Cells with value 0 | 1 | <-> | 4 |
+---+ +---+
+---+
Cells with value 1 | 0 |
+---+
+---+ +---+
Cells with value 2 | 2 | <-> | 3 |
+---+ +---+
Чтобы распечатать верхние k элементов за время O (k), вы начинаете со связанного списка с наибольшим значением и печатаете элементы там. Если этого недостаточно, то go перейдите ко второму по величине списку значений и напечатайте его содержимое, затем следующий список, затем следующий и т. Д. c.
Задача состоит в том, как сохранить эти отдельные связанные списки. Нам нужно сделать следующее:
Определить, в каком связанном списке находится конкретная ячейка, чтобы мы могли поднять его до следующего уровня.
Определите, какое числовое значение c связано с конкретным связанным списком, поэтому, когда мы повышаем значение одной ячейки до более высокого, мы можем определить, перемещать ли ее в следующий список в серии или нам нужно создать новый список.
Удалить пустой список, значение которого больше не используется.
Перебирать списки в обратном порядке, поэтому мы может печатать верхние k элементов.
Одним из решений этой проблемы является представление списка списков с использованием другого списка с двумя связями. В частности, мы будем делать следующее:
Поддерживать двусвязный список списков. Каждая ячейка в «списке списков» будет хранить номер, связанный с ячейками в этом списке.
Поддерживать указатель на последнюю ячейку в «списке списков», чтобы мы могли может эффективно печатать верхние k элементов.
Аннотируйте каждую существующую ячейку указателем на ячейку «списка списков», чтобы при выполнении приращения мы могли определить, какой из них список принадлежит.
Например, то, что я рисовал так:
+---+ +---+
Cells with value 0 | 1 | <-> | 4 |
+---+ +---+
+---+
Cells with value 1 | 0 |
+---+
+---+ +---+
Cells with value 2 | 2 | <-> | 3 |
+---+ +---+
На самом деле будет выглядеть так:
+--------+---------+
| | |
v | |
+--------------------+ +---+ +---+
| Cells with value 0 | -> | 1 | <-> | 4 |
+--------------------+ +---+ +---+
^
| +-------------+
| | |
v v |
+--------------------+ +---+
| Cells with value 1 | -> | 0 |
+--------------------+ +---+
^
| +--------+---------+
| | | |
v v | |
+--------------------+ +---+ +---+
| Cells with value 2 | -> | 2 | <-> | 3 |
+--------------------+ +---+ +---+
^
|
+---- max
Это позволяет нам склеивать элементы из списка, выяснять, к какому списку они принадлежат, а затем определять, следует ли склеивать их в списке над нами или создавать новый список между двумя списками.
Каждый элемент в массиве использует пространство O (1) самостоятельно. Каждая ячейка «списка списков» занимает пробел O (1), и их не более n, поскольку по одному на каждое сохраненное значение. Каждое приращение занимает время O (1), а верхние k элементов можно найти за время O (k), отойдя назад от конца «списка списков» и распечатав значения. И при создании этой структуры данных не было никаких проблем. : -)
Надеюсь, это поможет!