问题:10亿个数,只有一个数出现一次,其他出现了两次,找出这个数。
利用Xθ0=X, XθX=0 (θ代表异或)。可以将这10亿个数求异或,即x1θx2θ.............xn得到的结果即为出现一次的数。控件O(1), 时间O(N)
另外位图法也是不错的尝试。
问题:10亿个数,只有一个数出现一次,其他出现了两次,找出这个数。
利用Xθ0=X, XθX=0 (θ代表异或)。可以将这10亿个数求异或,即x1θx2θ.............xn得到的结果即为出现一次的数。控件O(1), 时间O(N)
另外位图法也是不错的尝试。