O(n)算法,找到缺失的整数

Question

数组A包含范围为[0,n-1]的n-1个唯一整数,也就是说,此范围中有一个不在A中的数字.设计用于查找该数字的O(n)算法.除阵列A本身外,仅允许使用O(1)额外空间.

需要一些帮助来解决这个问题,

Answer 1

1. 对数组求和.
2. 使用算术级数公式计算预期总和

给出这些值:一个是0 + 1 + 2 + ... + n-1,另一个是你的实际元素的总和 - 想想它们彼此之间的差异,另一个没有的东西.确保你知道它,答案是微不足道的.

编辑:(理论评论):
注意sum(array)需要2*log_2(max(arr))位.因此,如果您的元素都是32位整数,则最多需要64位来表示总和.
从纯粹的理论方法 - 它不是O(1).但是,您可以使用数组本身(它包含多个2*log_2(max(arr)) 位)来存储总和.