Пространственная сложность переменной, которая растет и уменьшается внутри функции

Question

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

В конце концов, hashTable будет содержать только символ, который встречался в массиве один раз.Какова будет сложность пространства для такой проблемы, как эта, где hashTable растет, а затем и уменьшается?

Я ожидаю, что сложность пространства равна O (1), поскольку независимо от размера ввода, окончательный размер hashTableбудет иметь длину 1.

* Примечание. Предположим, что во входном массиве дубликатов будет только 1 элемент, который встречается один раз, и вам не нужно беспокоиться о любых других крайних случаях.

Answer 1

Пространственная сложность - это не просто мера пространства, используемого вашим алгоритмом на конце алгоритма при идеальных обстоятельствах.Как правило, это мера того, сколько ваш алгоритм требует для решения.В вашем случае, поскольку он должен циклически проходить и потенциально запоминать весь входной массив один раз (при условии правильной реализации хеш-таблицы с доступом для чтения / записи O (1)), это O (n) - даже при условии, что есть только парыдубликаты и одно значение.Нотация заказа обычно не принимает во внимание что-то вроде O (n / 2).

Как упоминалось в Nuno, ваш алгоритм не будет работать, если вам нужно принять во внимание трижды.Даже если в конкретном вопросе говорилось, что они не могут возникнуть сейчас, важно помнить о будущем - я использую вариант этого класса проблем в качестве вопроса для интервью, и люди часто забывают трижды.

Эти кандидаты не проходят.

Answer 2

Что если есть нечетное количество дубликатов?Хеш-таблица теряет значение, а затем снова получает его!

Правильный способ (я думаю) O (n) WCS - это использовать таблицу (необязательно хеш-таблицу, если вы ничего не хешируете).После этого удалите все значения больше 1 и вуаля. (Все еще O (n)).

Редактировать: Объяснение сложности: С точки зрения пространства, наихудший сценарий состоит в том, что каждое значение встречается один раз в исходном массиве.Это означает, что результирующая таблица имеет 1 запись для каждого члена исходного массива.Значение N записей.Этот алгоритм является вычислительно линейным.

Если бы вы действительно пытались разобраться в этом с точки зрения сложности, вам нужно было бы изменить вычислительные требования вашей "хеш-таблицы" - на самом деле использовать хеш?я могу предварительно выделить весь Counter-домен как массив целых чисел?Они на самом деле больше зависят от реального применения этого алгоритма.В любом случае это в основном супер быстрый алгоритм класса P.