Найдите пропущенное число в диапазоне {0 ...... 2 ^ k -1}

Question

Учитывая массив, который имеет номера {0......2^k -1} за исключением одного числа, найти хороший алгоритм, который находит недостающее число.

Обратите внимание, вы можете использовать только:

• для A[i] возвращает значение бита j.

• поменяйте местами A [i] с A [j].

Мой ответ: используйте «разделяй и властвуй», проверьте число бит K всех чисел, если бит K (теперь мы в LSB) равен 0, затем переместите число в left side, если K бит равен 1, затем переместите число на right side. После 1-й итерации у нас будет две группы, одна из которых больше другой, поэтому мы продолжаем делать то же самое с меньшей группой, и я думаю, что мне нужно проверить бит K-1 время.

Но по какой-то причине я попытался с 8 числами, из 0.....7, и удалил 4 (скажем, я хочу выяснить, что 4 - это пропущенное число), однако алгоритм не сработал так хорошо. Так где же моя ошибка?

Answer 1

Я предполагаю, что вы можете построить функцию xor bit, используя бит get j.

Ответ будет (xor всех чисел)

ДОКАЗАТЕЛЬСТВО: a xor (2^k-1-a) = 2^k-1 (a и (2 ^ k-1-a) будут иметь разные биты в первых k позициях).
Тогда 0 xor 1 xor ... xor 2^k-1 = (0 xor 2^k-1) xor (1 xor 2^k-2).... (2^(k-1) pairs) = 0.
если число n отсутствует, результатом будет n, потому что 0 xor 1 xor 2....xor n-1 xor n+1 xor ... = 0 xor 1 xor 2....xor n-1 xor n+1 xor ... xor n xor n = 0 xor n = n

РЕДАКТИРОВАТЬ: Это не будет работать, если k = 1.

Answer 2

Рон

ваше решение верное. Эта проблема пахнет быстрой сортировкой, не так ли?

То, что вы делаете с битом Kth (все 0 слева, 1 справа), называется разделением - вам нужно найти неупорядоченные элементы попарно и поменять их местами. Это процесс, используемый в выделении Хоара и в быстрой сортировке со специальной классификацией элементов - не нужно использовать элемент поворота.

Вы забыли указать в постановке задачи, сколько элементов в массиве (2 ^ k-2 или более), т. Е. Если разрешены повторы.

Если повторы не разрешены, каждый раздел действительно будет разбалансирован одним элементом. Используемый алгоритм является экземпляром Hoare's Selection (только разделите наименьшую половину). На каждом этапе разбиения количество рассматриваемых элементов уменьшается вдвое, следовательно, O (N) время выполнения. Это оптимально, поскольку каждый элемент должен быть известен до того, как будет найдено решение.

[Если повторы разрешены, используйте измененную Быструю сортировку (рекурсивно разбивайте обе половины), пока не получите пустую половину. Время работы, вероятно, составляет O (N Lg (N)), но это необходимо проверить.]

Вы говорите, что алгоритм провалился в вашем тестовом примере: вы, вероятно, неправильно реализовали некоторые детали.

Пример:

Начните с 5132670 (это диапазон {0..7})

После разбиения на битовый вес = 4 вы получите 0132 | 675

где самая короткая половина 675 (это диапазон {4..7})

После разбиения на битовый вес = 2 вы получите 5 | 67

где самая короткая половина 5 (это диапазон {4..5})

После разбиения на битовый вес = 1, вы получите | 5

где самая короткая половина пуста (это диапазон {4}). Готово. * * 1029

Answer 3

для n просто сложите их все и вычтите результат из n * (n + 1) / 2
n * (n + 1) / 2 - сумма 1 ... n всех чисел.Если один из них отсутствует, то сумма этих n-1 чисел будет n * (n + 1) / 2- missingNumber
Ваш ответ: n * (n + 1) / 2- missingNumberгде n равно 2 ^ k-1

Answer 4

вы можете рассматривать элементы как строку из k битов, и на каждом шаге i, если число единиц или нулей в позиции i равно 2 ^ (k-i), вы должны удалить все эти строки, например, продолжить 100 111 010 101 110 000 011 так 100 111 101 110 все будет удалено и между 010 000, 011, 010 и 011 будут удалены, потому что их второй бит равен 1 000 остается, а его самый правый бит равен нулю, поэтому 001 - отсутствующее число

Answer 5

Учитывая тот факт, что для данной битовой позиции j, есть ровно 2^(k-1) чисел, для которых установлено значение 0, и 2^(k-1), для которых установлено значение 1, используют следующий алгоритм.

 start with an array B of boolean of size k 
 init the array to false everywhere
 for each number A[i]
   for each position j 
    get the value v
    if v is 1 invert the boolean at position j
   end for
 end for

Если позиция в конце ложна, то у пропущенного числа есть ноль в этой позиции, в противном случае он равен единице (для k >1, если k = 1, то это обратное значение).Теперь для реализации вашего массива логических значений создайте число размером 2k, где нижний k установлен на 0, а верхний на 1.Тогда

invert the boolean at position j 

- это просто *

 swap B[j] with B[j+k].

. В этом представлении отсутствующее число является нижними k элементами массива B.Ну, этот алгоритм все еще O(k*2^k), но вы можете сказать, что это O(n*log(n)) от ввода.