Поиск одного номера в списке
Какой будет лучший алгоритм для нахождения числа, которое встречается только один раз в списке, в котором все остальные числа встречаются ровно дважды.
Итак, в списке целых чисел (давайте возьмем его как массив) каждое целое число повторяется ровно дважды, кроме одного. Чтобы найти тот, который является лучшим алгоритмом.
11 ответов
Самый быстрый (O(n)) и самый эффективный способ памяти (O(1)) - это операция XOR.
В С:
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!= 0, так как a!= B. Выберите любой 1 бит a ^ b и используйте его в качестве маски - более подробно: выберите x как степень 2, чтобы x & (a^b) было ненулевым.
Теперь разделите список на два подсписка - один подсписок содержит все числа y с y&x == 0, а остальные идут в другом подсписке. По тому, как мы выбрали x, мы знаем, что a и b находятся в разных сегментах. Мы также знаем, что каждая пара дубликатов находится в одном и том же сегменте. Таким образом, теперь мы можем независимо применить трюк "XOR-em-all" к каждому сегменту и выяснить, что такое a и b.
Bam.
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
Метод сортировки и метод XOR имеют одинаковую сложность по времени. Метод XOR - только O(n), если вы предполагаете, что побитовое XOR двух строк является операцией с постоянным временем. Это равносильно тому, что размер целых чисел в массиве ограничен константой. В этом случае вы можете использовать Radix sort для сортировки массива в O(n).
Если числа не ограничены, то для побитового XOR требуется время O (k), где k - длина строки битов, а для метода XOR - O (nk). Теперь снова Radix sort будет сортировать массив по времени O (nk).
Зависит от того, насколько большие / маленькие / разнообразные числа, хотя. Может быть применена радикальная сортировка, которая значительно сократит время сортировки решения O(N log N).
Вам нужно указать, что вы подразумеваете под "лучшим" - для некоторых скорость - это все, что имеет значение, и ответ на этот вопрос будет считаться "лучшим" - для других они могут простить несколько сотен миллисекунд, если решение будет более читабельным.
"Лучший" является субъективным, если вы не более конкретны.
Это говорит:
Перебирайте числа, для каждого номера ищите список по этому номеру, и когда вы достигнете числа, которое возвращает только 1 для числа результатов поиска, все готово.
Похоже, лучшее, что вы могли бы сделать, - это перебрать список, для каждого элемента добавить его в список "увиденных" элементов или удалить его из "увиденного", если он уже есть, и в конце список "увиденных". "элементы будут включать в себя единичный элемент. Это O(n) в отношении времени и n в отношении пространства (в худшем случае будет намного лучше, если список отсортирован).
Тот факт, что они являются целыми числами, на самом деле не учитывает, так как нет ничего особенного, что вы можете сделать, добавив их... не так ли?
Вопрос
Я не понимаю, почему выбранный ответ "лучший" по любым стандартам. O(N*lgN) > O(N), и он меняет список (или создает его копию, которая все еще дороже в пространстве и времени). Я что-то пропустил?
Вы можете просто поместить элементы в наборе в хеш, пока не найдете столкновение. В рубине это однострочник.
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