Алгоритм для поиска нечетного элемента (без пар) в массиве?

Можно создать дубликат:
Finding a single number in a list Алгоритм для поиска нечетного элемента (без пар) в массиве?

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

Возможно, что-то по строкам двоичного поиска, например, суммирует все элементы из 2 небольших массивов размером n/2, сравнивают рекурсивно узнают?

Edit:

Является ли этот алгоритм XOR фактически предполагая {1,1,4,4,7,7,5,8,8,9,9}? Моим вкладом может быть и randmon - {1,4,1,8,9,5,4,5,9,8}. Итак, логика меняется в этом случае?

источник

2011-02-03 Nishant

О, я предложил этот бинарный поиск, так как я ошибочно принял массив, чтобы иметь одинаковые элементы, кроме нечетного, например, аналогичный пример шара - в этом случае двоичный файл, вероятно, будет хорошим! XOR кажется интересным. – Nishant

Будет ли этот алгоритм работы XOR работать, если элементы случайным образом сохранены, а один - ODD. – Nishant

Попробуйте вручную, это поможет вам понять, как это работает. – AakashM

XOR все элементы массива. Результатом будет элемент, который повторяется нечетное число раз.

источник

2011-02-03 08:01:58 codaddict

Это случай, если элементы хранятся случайным образом? Не только пары? – Nishant

@Nishant: порядок элементов не имеет значения. Попробуйте сами: 'arr = [1 2 3 2 1]' – codaddict

xor все элементы в массиве.

источник

2011-02-03 08:01:47 zvrba

Эксклюзивные или все вместе.

источник

2011-02-03 08:01:54

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

источник

2011-02-03 08:02:40 gprasant

Всего xor все числа в массиве. Результатом является число, которое появляется нечетным временем. Это верно, так как число xor одинаковое число дает 0. Если вы запустите его даже раз, результат снова будет 0. Но если вы запустите его нечетные раз, результат будет 0 xor number = number.

источник

2011-02-03 08:03:02

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

[TestMethod] 
public void SumOfPairs() 
{ 
    var nums = new[] { 1, 1, 4, 4, 7, 7, 5, 8, 8, 12, 12 }; 
    int i = 0; 
    foreach (var num in nums) 
    { 
     i ^= num; 
    } 

    Assert.AreEqual(5, i); 
}

Обратите внимание, что это не сработает, если не указаны точные условия, которые вы указали.

источник

2011-02-03 08:04:12

Алгоритм для поиска нечетного элемента (без пар) в массиве?

ответ

Смежные вопросы