Алгоритм для поиска числа, который встречается только один раз в массиве, если все остальные числа встречаются дважды

Ответ 1

Ответ в 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 все! HAHAHAH!

Rampion напомнил мне об инъекционном методе, поэтому вы можете сделать это в одной строке:

def singleton(array) array.inject(0) { |accum,number| accum ^ number }; end

Ответ 2

Предполагая, что вы можете XOR цифры, то есть ключ здесь, я считаю, из-за следующих свойств:

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

Итак, если вы просто 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) дополнительное пространство (всего одно маленькое целое число).

Ответ 3

"Проведите анализ массива и увеличьте число для числа."

Вы можете изменить это на "Разбор массива, и если номер уже существует в хеш-таблице, удалите номер из хеш-таблицы". Затем шаг 3 просто "получает единственное число, которое остается в хеш-таблице"

Ответ 4

Учитывая массив целых чисел, каждый элемент появляется дважды, кроме одного. Найдите этот единственный. Мы можем использовать операцию XOR. Поскольку каждое число XOR само по себе, результаты будут равны нулю. Итак, мы XOR каждое целое число в массиве, и результат - единственный, который мы хотим найти. Вот код версии java:

public class Solution {
    public int singleNumber(int[] A) {
        int res=0;
        for(int i=0;i<A.length;i++){
            res=res^A[i];
        }
        return res;
    }
}

Последующие действия 1: Учитывая массив целых чисел, каждый элемент появляется три раза, за исключением одного. Найдите этот единственный. Заметка: Ваш алгоритм должен иметь сложность линейного выполнения. Не могли бы вы реализовать его без использования дополнительной памяти? Для этой проблемы мы не можем использовать операцию XOR. Лучший способ решить эту проблему - использовать "бит-счет". Создайте 32 массива int int array [32]. count [i] означает, сколько "1" в i-м бите всех целых чисел. Если count [i] можно разделить на 3, тогда мы проигнорируем этот бит, иначе мы выведем этот бит и сформируем результат. Ниже приведен код Java-версии:

public class Solution {
    public int singleNumber(int[] A) {
        int res=0;
        int[] count=new int[32];
        for(int i=0;i<32;i++){
            for(int j=0;j<A.length;j++){
                if(((A[j]>>i)&1)==1){
                    count[i]=count[i]+1;
                }
            }
            if((count[i]%3)!=0){
                res=res|(1<<i);
            }
        }
        return res;
    }
}

Последующие действия 2: Учитывая массив целых чисел, каждый элемент появляется дважды, за исключением двух. Найдите два целых числа. Решение: Во-первых, XOR всех целых чисел в массиве мы можем получить результат (предположим, что c) Во-вторых, от младшего значащего разряда до самого значимого бита найдите первую позицию "1" (предположим, что позиция равна p). В-третьих, разделили целые числа на две группы, позиция p - "1" в одной группе, "0" в другой группе. В-четвертых, XOR - все целые числа в двух группах, а результаты - это два целых числа, которые мы хотим.

Ответ 5

Я ворую Майкл Динайер отвечает и переопределяет его в Python и C:

Python:

def singleton(array):
    return reduce(lambda x,y:x^y, array)

С

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 не имеет таких ограничений.

Ответ 6

Здесь решение в Python, которое превосходит Ruby для размера (и читаемость тоже, IMO):

singleton = lambda x: reduce(operator.xor, x)

Ответ 7

Решение 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
>>> 

• Пэдди.

Ответ 8

Algo 2:

• Сортировка массива.
• Теперь проанализируем массив, и если два последовательных номера не совпадают, мы получили наш номер.
• Это не будет использовать дополнительное пространство

Ответ 9

Это не соответствует счету "без лишнего пространства", но он сократит пространство, если номера не будут отсортированы определенным образом.

В 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