一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。...输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
限制:
1 <= 数组长度 <= 10000
解题思路
解法1:二分
1,这是一个二分查找的变形...2,有个特殊点需要注意
3,如果 数组中,没有缺失的,那么缺失的在末尾
4,如果中间位置值和下标相等,则不用查找左边。...解法二:异或
^= 位逻辑异或赋值,是一个复合赋值运算符
异或就是两个数的二进制形式,按位对比,相同则取0。...0^0→0 , 0^1→1 , 1^0→1 , 1^1→0
任何数与0异或等于它本身,即a^0=a
一个数与自己异或结果为0,即a^a=0
令0~n的数与nums中的数异或,运算中除了缺失值只出现一次外