求1--100丢失的数

假定一个数组的容量ARR是99，里面含有1--100这100个数里的99个，不重复，如何快速地定位到缺失的那个数。算法的复杂度是？

 

如果数组是有序的，也就是，1,2,3。。。。。。那么任何相邻的两个数（两数都是连续的）之间的差值的绝对值是1，如果存在不连续的情况，也就是差值的绝对值是不等于1，实际上等于2.那么这两个数之间的数便是缺失的数。也就是An-1 + 1，或者An - 1

 

如果数组是无序的，我们可以经过排序，然后再按照上述步骤进行。只是有些麻烦。其实我们都知道1+2+3+。。。100=5050。所以5050-sum(ARR)=result，求的的result便是缺失的数。