思路描述:假设 0~n-1 中没有数字 i ,那么这 n - 1 个数字的和为 sum = n*(n-1)/2 - i,那么 i = n*(n-1)/2 - sum。
其实我们可以注意到,从缺失的数字 i 开始下标和数值不相等
前两种做法时间复杂度均为 O(n),有没有更优的做法?由第二种做法我们知道,如果 k == nums[k],那么缺失的数字一定在 k 右边,如果 k != nums[k],那么缺失的数字要么为 k 要么在 k 左边;这个很类似于二分查找,我们也可以使用二分的思想去优化时间复杂度。
作者:yizhe-shi
链接:https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/solution/c-onolgnfang-fa-jie-da-by-yizhe-shi/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
原文:https://www.cnblogs.com/sweet-li/p/13160436.html