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

Question

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

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

Answer 1

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

В 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 с самим собой (более или менее). Единственный, который остается немаркированным, - это ваш не дубликат.

Answer 2

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

«Лучшее» является субъективным, если вы не более конкретны.

---

Это говорит:

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

Answer 3

O (N) время, O (N) памяти

HT = Hash Таблица

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

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

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

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

---

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

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

Answer 4

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

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

Answer 5

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

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

Вопрос

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

Answer 6

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

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 

Answer 7

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

Answer 8

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

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

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

Bam.

Answer 9

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

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

Answer 10

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

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

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

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

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

Answer 11

Реализация в 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