Найти недостающее число в целочисленном массиве

Question

мне дают якобы последовательный массив таким образом, как это:

{4,5,7,8,9,10} // missing 6 

И я должен эффективно найти недостающую 6.

Я думал о делать бинарный поиск и проверка середины +1, середины -1.

Но я продолжаю думать, что будет так много базовых корпусов. Я держу неудачу ...

Это не должно быть такой трудной проблемой, но я не знаю, почему я борюсь так трудно:/

Может кто-то наставит меня через это ??

Большое спасибо ПЕРЦЫ

Answer 1

В одном линейном проходе найти наименьший элемент, наибольший элемент, и сумма всех элементов.

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

Answer 2

Всегда keep it simple приятель. Вы всегда можете сделать это в N временной сложности.

int[] arr = new int[]{4,5,7,8,9,10}; 
     int missing=0; 
     for(int i=0;i<arr.length;i++) 
     { 

      int x = arr[++i]; 
      int y = arr[i] +1; 

      if(x != y) 
      { 
       missing = y; 
       break; 
      } 
     } 

     System.out.println(missing);