Поиск одного номера в списке [дублировать
https://stackoverflow.com/questions/35185
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Этот вопрос уже имеет ответ здесь:
Что было бы лучшим алгоритмом для поиска числа, которое происходит только один раз в списке, в котором все остальные числа встречаются ровно дважды.
Таким образом, в списке целых чисел (давайте возьмем его в качестве массива), каждое целое число повторяет ровно дважды, кроме одного. Чтобы найти это, какой лучший алгоритм.
Решение
Самый быстрый (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», который является единственным, который происходит один раз.
Это работает, потому что в первый раз, когда вы попадаете в число, он отмечает числовую переменную с самим собой, а во второй раз, когда он не смирится с самим собой (более или менее). Единственный, кто остается без опознавательного знака,-это не дубликат.
Другие советы
Кстати, вы можете расширить эту идею, чтобы очень быстро найти два Уникальные числа среди списка дубликатов.
Назовем уникальные номера A и B. Сначала возьмите Xor всего, как предложил Кайл. То, что мы получаем, это^b. Мы знаем^b! = 0, так как A! = B. Выберите любой 1 бит A^B и используйте его в качестве маски - более подробно: выберите X в качестве силы 2, чтобы x & (a^b) ненулея.
Теперь разделите список на два сублиста - один сублист содержит все числа y с Y & X == 0, а остальные идут в другой сублист. Кстати, мы выбрали X, мы знаем, что A и B находятся в разных ведрах. Мы также знаем, что каждая пара дубликатов все еще находится в одном ведре. Таким образом, теперь мы можем применить Ye Olde «Xor-Em-All», к каждому ведру независимо и обнаружить, что такое A и B полностью.
Бам.
O (n) время, o (n) память
HT = хэш -таблица
Ht.clear () перейдите по списку для каждого элемента, который вы видите
if(HT.Contains(item)) -> HT.Remove(item)
else
ht.add(item)
В конце концов, предмет в HT - это товар, который вы ищете.
Примечание (Credit @Jared adpure): эта система найдет все странные экземпляры элементов.
комментарий: Я не понимаю, как люди могут голосовать за решения, которые дают вам производительность NLOGN. В какой вселенной это «лучше»? Я еще более шокирован, что вы отметили принятый ответ на решение ...
Однако я согласен с тем, что если память должна быть постоянной, то NLOGN будет (до сих пор) лучшим решением.
Решение Кайла, очевидно, не поймет ситуации, если бы набор данных не соблюдает правила. Если бы все числа были в парах, алгоритм дал бы результат нуля, то такое же значение, как если бы ноль было единственным значением с единственным событием.
Если бы было несколько значений за один раз или тройки, результатом также был бы ошибочный.
Тестирование набора данных вполне может получить более дорогостоящий алгоритм, либо в памяти, либо времени.
Решение CSMBA показывает некоторые данные об ошибке (нет или более, чем одно значение единого происхождения), но не другое (Quadrouples). Что касается его решения, в зависимости от реализации 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 для количества результатов поиска, вы закончите.
Похоже, что лучшее, что вы могли бы сделать, это итерация через список, для каждого элемента добавить его в список «виден» предметов или удалить его из «В виде», если он уже там, и в конце ваш список ». «Предметы будут включать в себя единственный элемент. Это O (n) в отношении времени и n в отношении космоса (в худшем случае будет намного лучше, если список отсортирован).
Тот факт, что они целые числа на самом деле не учитывают, так как нет ничего особенного, что вы не можете сделать с добавлением их ... там?
Вопрос
Я не понимаю, почему выбранный ответ «лучший» по любым стандартам. O (n*lgn)> o (n), и он меняет список (или иначе создает его копию, которая еще дороже в пространстве и времени). Я что-то пропустил?
Зависит от того, насколько большие/маленькие/разнообразные числа. Можно применить сортировку Radix, что уменьшит время сортировки решения O (N Log N) в значительной степени.
Метод сортировки и метод XOR имеют одинаковую сложность. Метод XOR составляет только O (n), если вы предполагаете, что бить XOR из двух строк является постоянной работой времени. Это эквивалентно сказать, что размер целых чисел в массиве ограничен постоянной. В этом случае вы можете использовать Radix Sort для сортировки массива в O (n).
Если цифры не ограничены, то бить XOR занимает время O (k), где k - длина битовой строки, а метод XOR принимает O (NK). Теперь снова Radix Sort сортирует массив во времени O (NK).
Вы можете просто поместить элементы в набор в хэш, пока не найдете столкновение. В Ruby это однострочная.
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+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
