Поиск единственного числа в списке

Самый быстрый (O (n)) и наиболее эффективный с точки зрения памяти (O (1)) способ - это операция XOR.

In C:

int arr[] = {3, 2, 5, 2, 1, 5, 3};

int num = 0, i;

for (i=0; i < 7; i++)
    num ^= arr[i];

printf("%i\n", num);

Это печатает «1», единственное, что встречается один раз.

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

Кстати, вы можете расширить эту идею, чтобы очень быстро найти два уникальных числа в списке дубликатов.

Назовем уникальные числа a и b. Сначала возьмите XOR всего, как предложил Кайл. Мы получаем a ^ b. Мы знаем, что a ^ b! = 0, поскольку a! = B. Выберите любой 1 бит a ^ b и используйте его как маску - более подробно: выберите x как степень двойки, чтобы x & (a ^ b) было ненулевым.

Теперь разделите список на два подсписка - один подсписок содержит все числа y с y & x == 0, а остальные входят в другой подсписок. Кстати, мы выбрали x, мы знаем, что a и b находятся в разных сегментах. Мы также знаем, что каждая пара дубликатов все еще находится в одной корзине. Итак, теперь мы можем применить старый трюк «XOR-em-all» к каждому сегменту независимо и полностью выяснить, что такое a и b.

Бам.

Время O (N), время O (N)

HT = Хеш-таблица

HT.clear () просмотрите список для каждого элемента, который вы видите

if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)

в конце элемент HT - это элемент, который вы ищете.

Примечание (кредит @Jared Updike): эта система найдет все нечетные экземпляры предметов.

комментарий: я не понимаю, как люди могут голосовать за решения, обеспечивающие производительность NLogN. в какой вселенной это «лучше»? Я еще более шокирован, что вы отметили принятый ответ как решение NLogN ...

Однако я согласен с тем, что если требуется постоянная память, то NLogN будет (пока) лучшим решением.

Решение Кайла, очевидно, не могло бы уловить ситуации, если бы набор данных не соответствовал правилам. Если бы все числа были парами, алгоритм дал бы результат ноль, точно такое же значение, как если бы ноль был бы единственным значением с единичным случаем.

Если бы было несколько одиночных значений или троек, результатом также была бы ошибка.

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

Решение Csmba действительно показывает некоторые данные об ошибках (не более одного значения одного появления), но не другие (четверные). Что касается его решения, в зависимости от реализации HT память и / или время больше O (n).

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

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

И теперь проблема в том, чтобы найти «лучший» алгоритм сортировки. Существует множество алгоритмов сортировки, каждый из которых имеет свои сильные и слабые стороны, так что это довольно сложный вопрос. Запись в Википедии кажется хорошим источником информации по этому поводу.

Реализация на Ruby:

a = [1,2,3,4,123,1,2,.........]
t = a.length-1
for i in 0..t
   s = a.index(a[i])+1
   b = a[s..t]
   w = b.include?a[i]
   if w == false
       puts a[i]
   end
end

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

«Лучшее» - это субъективно, если вы не конкретизируете его.

При этом сказано:

Итерируйте по числам, для каждого числа выполните поиск в списке для этого числа, и когда вы достигнете числа, которое возвращает только 1 для количества результатов поиска, все готово.

Похоже, лучшее, что вы могли сделать, - это перебрать список, для каждого элемента добавить его в список «просмотренных» элементов или удалить его из «просмотренного», если он уже есть, и в конце вашего списка «увиденных» "items будет включать единственный элемент. Это O (n) по времени и n по пространству (в худшем случае будет намного лучше, если список будет отсортирован).

Тот факт, что они целые числа, на самом деле не учитывается, поскольку вы ничего особенного не можете сделать, чтобы их сложить ...

Вопрос

Я не понимаю, почему выбранный ответ «лучший» по любым стандартам. O (N * lgN)> O (N), и он изменяет список (или создает его копию, что по-прежнему дороже в пространстве и времени). Я что-то упускаю?

Однако зависит от того, насколько велики / малы / разнообразны числа. Может применяться поразрядная сортировка, которая значительно сократит время сортировки решения O (N log N).

Метод сортировки и метод XOR имеют одинаковую временную сложность. Метод XOR - это только O (n), если вы предполагаете, что побитовое XOR двух строк является операцией с постоянным временем. Это эквивалентно тому, что размер целых чисел в массиве ограничен константой. В этом случае вы можете использовать сортировку Radix для сортировки массива за O (n).

Если числа не ограничены, то побитовое XOR занимает время O (k), где k - длина битовой строки, а метод XOR принимает O (nk). Теперь снова Radix sort отсортирует массив за время O (nk).

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

def find_dupe(array)
  h={}
  array.detect { |e| h[e]||(h[e]=true; false) }
end

Итак, find_dupe([1,2,3,4,5,1]) вернет 1.

На самом деле это распространенный вопрос на собеседовании с "уловкой". Обычно речь идет о списке последовательных целых чисел с одним дубликатом. В этом случае интервьюер часто просит вас использовать трюк с гауссовой суммой n -целых чисел, например n*(n+1)/2 вычтено из фактической суммы. Ответ из учебника примерно такой.

def find_dupe_for_consecutive_integers(array)
  n=array.size-1   # subtract one from array.size because of the dupe
  array.sum - n*(n+1)/2
end