题目:
消失的数字
数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?
示例:
输入【3,0,1】
输出:2
解答:
想法1:先排序后查找
但一个排序耗费的时间就不符合O(n),最快的排序O(n*logn)。(注意二分查找的基础是已经排好序的数组!)
想法2:相加再相减
把0~N加到一起再减去数组中的数,即可求得,并且时间复杂度就是O(n)
源码:
想法3:异或处理(O(n))
^对二进制位进行计算,
^的一些重要性质:
- 相同为0,相异为1.
- 0跟任何数^都为那个数本身(这个性质可以把0看成桥梁!)
- 两个相同的数进行异或,结果就是0
- 异或满足结合律和交换律。
我们无法将两个数组同时进行异或,但我们可以用0先跟第一个数组异或,然后用这个结果与另外一个数组进行异或,效果相同!
源码: