Сообщить о всех пропущенных числах в массиве целых чисел (представлен в двоичном виде)

Question

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

Вам предоставляется список L[1...n], который содержит все элементы от 0 до n, кроме одного. Элементы этого списка представлены в двоичном виде and are not given in any particular order, и единственная операция, которую мы можем использовать для доступа к ним, - это выбор j-го бита L [i] за постоянное время. Как найти пропущенный номер в O(n)?

Он смог ответить на этот вопрос (который, как мне кажется, имеет несколько решений, ни одно из которых не было слишком сложным). Например, следующий псевдокод решает вышеуказанную проблему:

Say all numbers are represented by k bits and set j as the least significant bit (initially the rightmost).<br> 1. Starting from j, separate all the numbers in L into two sets (S1 containing all numbers that have 1 as its jth bit, and S2 containing all numbers that have 0 in that position).<br> 2. The smaller of the two sets contains the missing number, recurse on this subset and set j = j-1

На каждой итерации мы уменьшаем размер набора вдвое. Итак, изначально у нас есть O (n), затем O (n / 2), O (n / 4) ... = O(n)

Однако последующий вопрос звучал так: «Что если в нашем списке L пропущено k чисел, и мы хотим сообщить все k чисел, сохраняя при этом O ( н) сложность и ограничения исходной задачи? как это сделать

Есть предложения?

Answer 1

bool J[1..n + 1]={false,false...}
int temp;

for(i = 1; i <= n; i++)
{
    temp=bitwisecopy of L[i];
    J[temp + 1]=true
}

for(i = 1; i <= n+1; i++)
{
    if(J[i]==false)
       print i + 1;
}

Лол, вот в чём суть ... Я думаю, что индексы могут быть испорчены.

Правильно ли я понимаю проблему? Мне было не совсем ясно, что именно подразумевалось под единственной операцией - доступом к j-му биту L [i].

Answer 2

Моя идея состоит в том, чтобы решить это следующим образом:

Допустим, 2 ^ M - это самая низкая степень 2, которая выше, чем N:

2^M>N,    2^M-1 <= N

теперь пройдитесь по всем числам от 1 до 2 ^ M-1 и сделайте битовое XOR между всеми числами (поскольку вы можете переходить только через бит J каждый раз, делайте это для каждой цифры отдельно - это то же самое)

результатом всех XOR будет число, которое вы ищете.

например: если N = 6, а пропущенное число равно 3:

M=3 => 2^M-1=7 =>
1 XOR 2 XOR 4 XOR 5 XOR 6 XOR 7 = 3 

Answer 3

Вы можете решить исходную проблему в O (n), просто выполняя линейный обход массива, пока не найдете число, которое не соответствует ожидаемому значению, например, так (да, я знаю, что использую массив целых чисел, чтобы приблизить массив битов, но концепция та же самая):

int[] bits = {1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0};
int bitIndex = 0;
for (int num = 1; num < Integer.MAX_VALUE; num++) {
    int numBits = (int) (Math.log(num) / Math.log(2)) + 1;
    int nextNum = 0;
    for (int index = 0; index < numBits; index++) {
        nextNum = (nextNum << 1) | bits[bitIndex + index]; 
    }
    if (nextNum != num) {
        System.out.println("Missing number:  expected=" + num + ", actual=" + nextNum);
        break;
    }

    bitIndex += numBits;
}

Если вы хотите напечатать все числа, которых нет в массиве, сохраняя время выполнения O (n), просто замените break; на num = nextNum;, чтобы продолжить проверку следующего номера.

Хотя есть некоторые потенциальные проблемы с этим подходом. Если пропущено несколько последовательных номеров, все ставки отключены. Кроме того, если число битов в num + 1 больше, чем число битов в num, а num отсутствует в массиве битов, то индекс битов будет не совпадать с данными.

Конечно, если допускается пропуск нескольких чисел, тогда проблема не решаема. Рассмотрим для примера:

{1,1,1,1,1,1,1}

В этом случае так же верно говорить, что у меня есть номера 1, 3 и 15, так же, как и то, что у меня есть только 127 или что у меня есть 7 и 15. Когда разрешено пропускать несколько последовательных значений, способ разбора битов по существу становится произвольным.

Так что, возможно, один из способов ответить на второй вопрос - это прочитать все биты в одно большое целое число и сказать: «у вас [очень большое число] и все числа до того, как оно пропущено». Тогда вы дали правильный ответ за O (n) раз.