查找整数数组

Question

我给出一个所谓的连续阵列像这样缺少数：

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

而且我应该高效地寻找失踪的6

我曾想过做的二分查找，并检查中+1，中-1。

但我一直在想会有这么多基础案例。我一直没有...

这不应该是这样一个困难的问题，但我不知道为什么我挣扎这么难：/

有人能指导我这个？

非常感谢guyz

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);