Поиск недостающего целого в массиве целых чисел

Question

Недавно я просмотрел книгу кодирования и наткнулся на эту интересную проблему.

Массив A содержит все целые числа от 0 до n, за исключением одного номера, который отсутствует . В этой задаче мы не можем получить доступ к целому целому числу в A с одной операцией. Элементы A представлены в двоичном формате, и единственная операция, которую мы можем использовать для доступа к ним, - это «получить j-й бит A [i]», который принимает постоянное время. Напишите код для , найдите отсутствующее целое число. Можете ли вы сделать это за 0 (n) времени?

Что делает книга, это пройти через трехстраничный процесс, объясняющий, как именно эта проблема может быть выполнена эффективно. Честно говоря, для меня это было немного TL, DR, поэтому я сделал свое решение и сравнил его с книгой. Мне просто интересно, работает ли мое решение на самом деле или нет (так как кажется подозрительным, что ответ книги может быть таким длинным и подробным, когда более легкое решение может быть составлено за несколько минут).

Это решение книги:

1 public int findMissing(ArrayList<BrtInteger> array) { 
2  I* Start from the least significant bit, and work our way up */ 
3  return findMissing(array, 0); 
4 } 
5 
6 public int findMissing(ArrayList<Bit!nteger> input, int column) { 
7  if (column >= BitInteger.INTEGER_SIZE) { // We're done! 
8   return 0; 
9  } 
10  ArrayList<BitInteger> oneBits = 
11   new ArrayList<BitInteger>(input.size()/2); 
12  ArrayList<BitInteger> zeroBits = 
13   new ArrayList<BitInteger>(input.size()/2); 
14 
15  for (Bitlnteger t : input) { 
16   if (t.fetch(column) == 0) { 
17    zeroBits.add(t); 
18   } else { 
19    oneBits.add(t); 
20   } 
21  } 
22  if (zeroBits. size() <= oneBits.size()) { 
23   int v = findMissing(zeroBits, column + 1); 
24   return (v « 1) | 0; 
25  } else { 
26  int v = findMissing(oneBits, column + 1); 
27  return (v « 1) | 1; 
28 } 
29 } 

Мое собственное решение, которое мне кажется, то же O (п) сложность, но это делается в месте с O (1) пространства сложности, много проще. Я определяю метод «выборки» как взятие двух параметров. Первый указывает бит xth, а второй указывает номер индекса. Я пришел к предположению, что этот метод был дан, поскольку он упоминался в проблеме как таковой («получить j-й бит A [i]»). В основном, я просто проверяю, меняется ли младший бит между 1 и 0, - вот и все.

int findMissing(int[] arr) { 
    int lowBit = fetch(0, 0); // fetch the 0th bit of arr[0] 
    if(lowBit != 0) { 
     return 0; // obviously, the array is not starting at 0, so 0 must be what is removed 
    } 
    int expectedNextBit = 1; // we expect the lowest bit to be 1 
    for(int x = 1; x < arr.length; x++) { 
     lowBit = fetch(0, x); // fetch the 0th bit (lowest) of arr[x] 
     if(lowBit != expectedNextBit) { 
      return x; 
     } 
     expectedNextBit = lowBit^0x1; 
    } 
    return arr.length; 
} 

Мой вопрос: что случилось с моим собственным решением? Я студент-второкурсник CS, и книга написана PHD, поэтому я очень сомневаюсь, что мой ответ действительно может быть лучше, чем у них.

Answer 1

Ваше решение неверно предполагает, что номера ввода отсортированы. Если ваш вход был [0, 2, 1, 3, 5], тогда ваше решение неправильно сообщило бы 1, хотя оно появится позже в массиве.