Вопрос:

Найти, если массив имеет дубликаты за O (N) времени со вспомогательной структурой

c arrays time duplicates

55 просмотра

1 ответ

6 Репутация автора

Я хочу знать, возможно ли найти, если массив имеет дубликаты за O (N) времени в C, но вы можете использовать вспомогательную структуру данных, например, хеш-таблицу. Помните, что вставка в структуру данных также имеет значение для времени. Спасибо за внимание.

Автор: Jaln Источник Размещён: 06.01.2018 11:37

Ответы (1)


1 плюс

19480 Репутация автора

Решение

Да, хеш-таблица может работать.

Для каждого слова вы вычисляете хеш и пытаетесь вставить его в таблицу. Если корзина не пустая, вы сравниваете слова в корзине, а если новое слово не существует, вы добавляете его в корзину, иначе вы нашли дубликат.

Это означает, что вы обрабатываете слова ввода только один раз, однако вам может понадобиться проверять слова в контейнерах несколько раз.

Обработка ввода - это O (N), обработка сегментов - это функция размера хеш-таблицы.

Таблица размера 1 приведет к проверке каждого слова N раз, поэтому будет O (N 2 ). Размер таблицы N приведет к проверке каждого слова 0 раз, и поэтому будет O (N).

Автор: Paul Ogilvie Размещён: 06.01.2018 11:49
Вопросы из категории :
32x32