Поиск отсутствующего элемента в массиве

Question

Array A содержит n-1 уникальных целых чисел в диапазоне [0, n-1], то есть есть один номер из этого диапазона, который не находится в A. Создайте O (n) - алгоритм времени для нахождения этого числа. Вы можете использовать только O (logn) дополнительное пространство помимо самого массива A.

Любой может помочь?

Answer 1

сумма последовательных целых чисел от 0 до n-1, S = n * (n-1)/2;
сумма массива, с = calcSum (массив)               // О (п) сложность, один цикл требуется

отсутствует число = S-S;

Сложность: О (п)
Пространство Сложность: O (1)

Answer 2

/** 
    * Time Complexity will be 
    * Arrays.sort(A) = O (n log n) 
    * Binary Search O (log n) 
    * 
    * Total Time Complexity = O (n log n) + O (log n) 
    * 
    * @param A 
    * @return 
    */ 
    private static int getMissingElement(int[] A) { 
     Arrays.sort(A); 

     int low = 0; 
     int high = A.length-1; 
     int missingElement = 0; 
     while (low <= high) { 
      int mid = (low + high)/2; 
      if (A[mid] != mid+1) { 
       high = mid - 1; 
       missingElement = mid +1; 
      } 
      else { 
       low = mid + 1; 
      } 
     } 
     if(missingElement == 0){ 
      return A.length+1; 
     } 
     return missingElement; 
    }