Как найти целое число в списке размером N за постоянное время?

Question

Свойства списка:

1. должен иметь размер N, где N - количество целых чисел

2. нет пустых клеток

3. числа могут быть не совсем последовательными (т. е. {-23,-15,-3,1,2,6,7,8,15,100})

4. Вставка / поиск должны быть в постоянном времени.

Моим первым инстинктом было использование хеш-таблицы, но это создавало неиспользуемые ячейки, в которых пропускались числа.

Есть ли способ создать такой список для проверки в постоянное время, существует ли число в этом списке?

Answer 1

Следуя моим комментариям, вы можете пойти с SetВ зависимости от вашего конкретного случая использования вы можете проверить такие вещи, как Java HashSet или LinkedHashSet, если вам нужно поддерживать порядок, который в соответствии с документом должен быть постоянным временем:

Как и HashSet, он обеспечивает постоянную производительность для основных операций (добавление, хранение и удаление), предполагая, что хеш-функция правильно распределяет элементы между сегментами.

Если вы ищете решения для других платформ, возможно, есть эквивалентные реализации или вы можете проверить исходный код Java и реализовать его самостоятельно.