260. Single Number III

260. Single Number III

思路:

划分数组

思路非常精巧。用异或所有数组,由于异或的性质,只有两个唯一且不等的出现的数字$x$,$y$被记录下来,记为$z$。可以推测,$z$比不为零,且第一个1要么来自$x$,要么来自$y$。同时可以根据这个“第一个1”是否在其他数字上存在,将数组划分为两部分,一组是带有$x$和成对的数字,另一组类似。

如此划分数组,同时异或其中一组,就可以得到$x$或者$y$。当然也可以通过上面的$z$异或其中一个数字来得到另一个数字。

Read more