Алгоритм для нахождения числа, которое происходит только однажды в массиве, учитывая все другие числа происходит, дважды [копируют]
Итераторы C++ являются обобщением понятия указателя; они делают его применимым к более широкому диапазону ситуаций. Это означает, что они могут использоваться, чтобы сделать, такие вещи как определяют произвольные диапазоны.
итераторы Java являются относительно немыми перечислителями (хотя не настолько плохо как C#; по крайней мере, Java имеет ListIterator и может использоваться для видоизменения набора).
8 ответов
Ответ в Ruby, предполагающий, что один синглтон, а все остальные - ровно два появления:
def singleton(array)
number = 0
array.each{|n| number = number ^ n}
number
end
irb(main):017:0> singleton([1, 2, 2, 3, 1])
=> 3
^ - это, кстати, побитовый оператор XOR. XOR все! ХАХАХА!
Рэмпион напомнил мне о методе инъекции, поэтому вы можете сделать это в одной строке:
def singleton(array) array.inject(0) { |accum,number| accum ^ number }; end
«Анализируйте массив и увеличивайте счетчик для числа».
Вы можете изменить это на «Проанализируйте массив и, если число уже существует в хэш-таблице, удалите число из хэш-таблицы». Затем шаг 3 - это просто «получить единственный номер, который остается в хеш-таблице»
Предполагая, что вы можете XOR чисел, я считаю, что это ключ здесь, из-за следующих свойств:
XORкоммутативен и ассоциативен ( поэтому порядок, в котором это выполняется, не имеет значения).- число
XOR, созданное с самим собой, всегда будет равно нулю. - zero
XORed с числом будет этим числом .
Итак, если вы просто XOR все значения вместе, все те, которые встречаются дважды, уравняют друг друга (давая 0) и одно оставшееся число ( n ) выполнит XOR с этим результатом (0), чтобы получить n .
r = 0
for i = 1 to n.size:
r = r xor n[i]
print "number is " + r
Хеш-таблица не требуется, у нее производительность O (n) и дополнительное пространство O (1) (всего одно маленькое целое число).
Вот решение на Python, которое превосходит решение Ruby по размеру (и читабельности тоже, IMO):
singleton = lambda x: reduce(operator.xor, x)
Алгоритм 2:
- Сортировка массива.
- Теперь проанализируйте массив и, если 2 последовательных числа не совпадают, мы получили наш номер.
- Это не будет использовать лишнее пространство
Я краду ответ Майкла Софейера и заново реализую его на Python и C:
Python:
def singleton(array):
return reduce(lambda x,y:x^y, array)
C:
int32_t singleton(int32_t *array, size_t length)
{
int32_t result = 0;
size_t i;
for(i = 0; i < length; i++)
result ^= array[i];
return result;
}
Конечно, версия C ограничена 32-битными целыми числами (которые могут быть тривиально заменены на 64-битные целые числа, если вы того пожелаете). Версия Python не имеет такого ограничения.
Это не соответствует счету за «без лишнего места», но это сократит пространство, если числа не будут отсортированы определенным образом.
В Python:
arr = get_weird_array()
hash = {}
for number in arr:
if not number in hash:
hash[number] = 1
else:
del hash[number]
for key in hash:
print key
Решение Python 3.1:
>>> from collections import Counter
>>> x = [1,2,3,4,5,4,2,1,5]
>>> [value for value,count in Counter(x).items() if count == 1 ][0]
3
>>>
- Paddy.