0~n-1中缺失的数字
0~n-1中缺失的数字
问题陈述
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
示例:
1 | 输入: [0,1,3] |
思路分析
对于查找类问题,可使用二分法解决。
由题意,该序列为0~n-1的递增序列中少掉了一个数字,故有,当nums[i]=i时可以知道前i个元素是没有缺失的,
代码实现
1 | class solution{ |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 淋竹调!
评论