Какую структуру данных построишь для поиска целочисленного значения в массиве без сортировки?

Структуры данных для поиска целочисленных значений без сортировки

Этот вопрос проверяет понимание trade-off между временем и памятью. В зависимости от требований можно выбрать несколько подходов.

Hash Set — оптимальное решение

Для большинства случаев HashSet — идеальный выбор. Он обеспечивает среднюю сложность O(1) для поиска:

int[] array = {5, 12, 3, 45, 7, 23, 8};
Set<Integer> hashSet = new HashSet<>(Arrays.asList(5, 12, 3, 45, 7, 23, 8));

// Поиск за O(1)
if (hashSet.contains(45)) {
    System.out.println("Найдено!");
}

Преимущества:

• Среднее время поиска O(1)
• Простая реализация
• Стандартное решение в большинстве случаев

Недостатки:

• Требует O(n) дополнительной памяти
• В худшем случае O(n) при плохой хеш-функции
• Хеш-коллизии могут снизить производительность

Bitmap / BitSet — для ограниченного диапазона

Если известен диапазон значений (например, 0-1000000), BitSet эффективен:

BitSet bitSet = new BitSet(1000001);
int[] array = {5, 12, 3, 45, 7, 23, 8};

// Построение за O(n)
for (int num : array) {
    bitSet.set(num);
}

// Поиск за O(1)
if (bitSet.get(45)) {
    System.out.println("Найдено!");
}

Преимущества:

• Экономный расход памяти (~1 бит на значение)
• Очень быстрый поиск O(1)
• Битовые операции максимально быстры

Недостатки:

• Работает только с неотрицательными числами
• Требует знания диапазона значений
• Неэффективен для разреженных данных

Trie (префиксное дерево) — для специальных случаев

Для целочисленных значений, представленных в двоичной системе:

class TrieNode {
    TrieNode[] children = new TrieNode[2];
    boolean isEnd = false;
}

class IntegerTrie {
    private TrieNode root = new TrieNode();
    private static final int BITS = 32;
    
    public void insert(int num) {
        TrieNode current = root;
        for (int i = BITS - 1; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (current.children[bit] == null) {
                current.children[bit] = new TrieNode();
            }
            current = current.children[bit];
        }
        current.isEnd = true;
    }
    
    public boolean search(int num) {
        TrieNode current = root;
        for (int i = BITS - 1; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (current.children[bit] == null) {
                return false;
            }
            current = current.children[bit];
        }
        return current.isEnd;
    }
}

Применяется когда:

• Нужен поиск по префиксу или битовому паттерну
• Нужно найти ближайшее число (для сетей, XOR задач)
• Работа с IP адресами или маршрутизацией

Индекс на основе модульной арифметики

Для специфических задач можно использовать хеширование с модульной арифметикой:

int[] index = new int[100];  // Размер = max значение
int[] array = {5, 12, 3, 45, 7, 23, 8};

// Построение индекса
for (int num : array) {
    if (num < index.length) {
        index[num] = 1;  // Флаг наличия
    }
}

// Поиск
if (num < index.length && index[num] == 1) {
    System.out.println("Найдено!");
}

Это фактически упрощённый BitSet.

Рекомендации по выбору

Финальный ответ

Для большинства собеседований правильный ответ — HashSet, так как:

• Не требует сортировки (как и требовалось)
• Обеспечивает O(1) поиск в среднем
• Простен в реализации
• Стандартное решение

Но будь готов обсудить: BitSet для оптимизации памяти, если диапазон значений известен, или Trie для специальных задач с битовыми операциями.