Хитрый алгоритм вопрос

Question

Можно создать дубликат:
Quickest way to find missing number in an array of numbers

Входной сигнал: несортированная массив А [1, .., N], который содержит все, кроме одного из целых чисел в диапазоне от 0, .., n

Проблема заключается в том, чтобы определить недостающее целое число в O (n) времени. Каждый элемент A равен , представленному в двоичном формате, и единственной доступной операцией является бит функции (i, j), который возвращает значение j-го бита A [i] и принимает постоянное время.

Любые идеи? Я думаю, что какой-то алгоритм разделения и покоя был бы правильным, но я не могу придумать, что именно я должен делать. Заранее спасибо!

Answer 1

Это математическое свойство, что сумма чисел между 1 и n где n является n(n+1)/2. Вы можете увидеть это 10:

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 
= (1+10) + (2+9) + (3+8) +(4+7) + (5+6) 
= 11 + 11 + 11 + 11 + 11 
= 55 

Так, расширением, это сумма чисел от 0 через n, так как вы просто добавить 0 к нему. Итак, что вы делаете, это добавить все числа и сохранить счет, а затем использовать эту формулу для определения недостающего.

Так, что-то вроде:

count = 0 
sum = 0 
foreach num in list: 
    sum = sum + num 
    count = count + 1 
missing = count * (count+1)/2 - sum 

Получение номера с bit(i,j) сложно, поэтому вам придется извлечь биты по отдельности и превратить их в реальные цифры для суммирования.

Answer 2

Это вопрос трюка, так как использование битового метода потребовало бы всего цикла каждого бита для каждого числа, что означает, что он автоматически станет O (n * j), где j - количество бит, представляющих n.

Я думаю, что paxdiablo получил его, предполагая, что вам разрешено решение, которое не использует бит-метод.

Answer 3

Вы можете использовать оператор XOR быстрее, чем добавление. Поскольку у вас есть доступ к каждому биту, вы будете делать побитовое XOR здесь. принцип будет использоваться здесь (А исключающее ИЛИ В XOR A) = В

например: (1 XOR 2 ИСКЛЮЧАЮЩЕЕ 3) исключающее ИЛИ (1 XOR 2) = 3

for i=0 to n 
{ 
Total=Total XOR i 
} 

foreach element in A 
{ 
Total=Total XOR element 
}