arrays - 数组 [1,2,3....n]。该系列中缺少一个数字。找出该数字的最佳方法是什么？

Question

会有一个从 1,2,3.... n 开始的数组。如果从数组中删除任何一个数字，那么找出删除数字的最佳方法是什么。

标签： arraysalgorithm

Answer 1

以下只是找到丢失的一种可能的方法。

如果n给定，则系列的总和1 + 2 + 3 + ... + n是，

S =  1 + 2 + 3 + ... + n
  = n * (n + 1) / 2

所以，最终，你知道S. 现在总结你给出的所有整数。让我们称之为S'。S和S'之间的区别(S - S')就是答案。

即使给定的整数是随机顺序的，这也将起作用。这将不需要binary search整数必须排序并且需要额外的nlogn时间。