Есть ли в массиве уникальный элемент?

Question

Я ищу наиболее эффективный алгоритм для проверки наличия в массиве уникального элемента. Результат не обязательно должен быть уникальным элементом, просто true или false соответственно. Я знаю, что могу достичь эффективности O (n) с помощью хеш-таблицы или чего-то подобного, но я все еще ищу результат, который также более эффективен в отношении пространства.

e- массив не отсортирован и содержит целые числа.

Answer 1

Если число возможных значений мало и известно заранее, вы можете использовать битовый массив (который будет O (n) во времени, O (n) в пространстве и потребует меньше места, чем хеш-таблица).

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

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

Answer 2

Существует три различных метода с различной пространственной и временной сложностью:

1) Два цикла: время O (n ^ 2), пространство O (1).

2a) Сортировать затемлинейная проверка: время O (nlogn) для общего случая, пространство: O (1).2b) Сортировка без сравнения (основание, подсчет, ...), затем проверка: время O (n), пробел O (n)

3) Хеш-таблица или массив для хранения членства: время O (n),пробел O (n).

Таким образом, вы должны выбрать 2a (ограничение по пространству) или 3.

Answer 3

В php есть функция array_keys () .

array array_keys ( array $input [, mixed $search_value [, bool $strict = false ]] )

Если установлен необязательный параметр $ search_value, функция будет возвращать только ключи найденных значений.если в ответе есть только ключ массива, значит, значение должно быть уникальным.

Полагаю, мой ответ немного специфичен для (языка), и я не знаю, о чем говорит эта функция,Вы должны проверить это самостоятельно.:)

[Обновление]: я нашел в этой статье , в которой описывается, что array_keys () - это O (n).

Answer 4

Я не уверен насчет O (n), но с O (n ^ 2) вы можете взять элемент и сохранить его в порядке с другими элементами