Каждому числу соответствует другое число.
1 = 10
2 =15
3 = 15
9 = 11
8 = 11
Числа упорядочены, но могут быть пропуски.
Какой функционал нужен:
1) Найти максимум, если их несколько, то выбрать рандомный. Т.е. максимальные (2 =15, 3 = 15), то рандомом выбирается 2 или 3.
2) Изменить значение одного числа, например было (8 = 11), то теперь (8=12)
Мысли такие, но может что-то более подходящее. Ибо это довольно узкий момент в производительности. var my_data = new Dictionary<int, int>();
Методы, запись в структуру, я сам могу найти, для меня сейчас важен формат хранения.
Хотя если есть неочевидные и быстрые методы для конкретных структур, то я буду признателен.
Ну по асимптотике, добавление эл-та в HashMap (А Dictionary — это оно и есть), — это O(n)
(На самом деле нет. Если код не для CodeForces, то можно считать что O(1), потому что вероятность коллизии не большая)
Если устраивает такая, то вполне можно использовать.
А максимальное запоминать при вставке. Тогда получение макс будет O(1).
Алексей Лебедев: Смена максимального значение — является операцией вставки.
Какая разница, как часто оно меняется, если без коллизий это будет константой по времени?
Использовать multimap. Хранить в обратном порядке.
10 = 1
15 = 2
15 = 3
11 = 9
11 = 8
Последние члены контейнера имеют максимальные значения
Все подобные контейнеры имеют два варианта реализации - через деревья и через хештаблицы. Через деревья быстрее для вставки, через таблицы быстрее для чтения. Но лучше как вам говорят использовать накопление максимального количества в отдельной переменной.
Вставляется в самом начале, потом почти не вставляется. Но очень часто меняются значения, так, что максимум хранить не удобно. Да и максимумов может быть много.
