今天这题也太难了吧,又是困难题.
找出1到n之间两个缺少的数,并且时间复杂度是n,空间复杂度是1.
看了官方的解法,啃了特别久终于懂了.
所有xorsum先加全部数字,再加一遍1到n.相当于出现的数字搞了两次都抵消了.
剩下的xorsum就变成了a和b的异或了.
那么知道了有啥用呢?
a和b的异或,就说明a和b哪些位不同,本来a和b就肯定不同,所以肯定有1存在.
但可能有很多1,也有可能只有一个1.但我们要找出一位不同的来,也就是随便找一个1.
怎么找呢,就用x & -x来做,一个数和自己相反数按位与,结果就是只有一个1,那便是最右边最末尾的那个1.
找到了某一位是不同的之后,就把所有数字分成两类,一类是这一位是0的,一类是这一位是1的.
遍历一遍所有数字,再遍历一遍1到n,这样异或一遍之后.剩下的一组是a,另一组是b,答案就出来了.
这道题属实是太牛逼了,简直是面试神体,应该不提出苛刻的要求,让面试者来做,然后做完后层层递进提问.