在一个整数数组中找到一个缺失的数字。

Question

在一个整数数组中找到一个缺失的数字。

4

我被给予一个连续的数组，例如：

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

我需要高效地找到丢失的数字6。

我考虑过进行二分查找，并检查mid +1，mid -1。

但我一直认为会有很多基本情况。我一直失败......

这不应该是一个难题，但我不知道为什么我如此艰难 :/

有人能指导我吗？？

非常感谢！

- smbl

虽然您已经收到了几个可能的答案，但我认为值得注意的是，如果您在一种方法上遇到困难，您需要转而寻找另一种方法。二分查找可能不是他们正在寻找的。有很多技巧可以解决这个问题，但最简单易懂的方法（在我看来）涉及一个for循环。 - thesentiment

使用二分查找是你能做的最好的事情...这是《编程珠玑》中的第一章。 - dharam

1

这个问题中的数组是_有序_的，而参考问题中的数组则是明确洗牌的。这使得可以使用更快的二分查找解决方案。 - Jan Špaček

如果数组已排序，则可以使用二分查找在log(n)时间内给出解决方案，这是真的。 - Kostas Kryptos

是的，数组已经排序了。这就是为什么我避免了线性搜索。 - smbl

这是您的log(n)时间复杂度的解决方案：https://dev59.com/B3I95IYBdhLWcg3w3iHG#30148865 - Kostas Kryptos

2个回答

1

在一次线性遍历中，找到最小元素、最大元素和所有元素的总和。

知道最小值和最大值，如果没有缺失，你可以计算出所有数字的总和（这是一个等差数列的求和）。从实际总和中减去它将给出你缺失的数字。

- Ishamael

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- swapyonubuntu · Accepted Answer

永远保持简单，伙计。你总是可以用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);