[LeetCode]136. Single Number 孤独的数字

两手一摊。时间复杂度真是神一样的存在。位运算也确实厉害。

题目描述:

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题目大意:

(手动翻译)给你一个整型数组,除了一个元素之外其他的元素都有两个。找到那个孤独的元素。

注意:

你的算法应该是线性时间复杂度。你能不使用额外的内存去实现这道题吗?


 

以前做算法题,就经常遇到超时的问题。我一直很疑惑,老子本地运行没有一点问题,可是你这OJ系统就是不让我过。是不是和我有仇?后来其实说到底还是代码的问题,或者说是思路、算法的问题。

不用额外的内存?也就是直接遍历一遍就找到了,而不是再开辟内存一个个计数。行。

至于线性,额如果我用两层的for循环应该也没问题吧。

抱着这样侥幸的心理,我写了如下代码:

        Submission Result: Time Limit Exceeded

Exceeded……

可是我确实想不到什么更好的办法了。这题我想不出有什么比计数更好的了。而要完成计数,就必须去再执行一次for循环。而这次for循环必定造成超时。好的我做不出来了。

于是我搜狗了一下,得到的结果是,可以用异或运算解决这个问题。原因是异或满足交换律,所以将所有的数字异或一遍,得到的结果一定是那个孤独的数字。

??!

过了一会儿才明白,我们人类在做异或运算的时候,应用交换律可以将相同的数字合在一起先做异或运算,得到的都是false。然后到最后false与那个孤独的数字做异或运算结果就是那个数字了。而机器就很刚猛,直接通过位运算去做异或运算,但结果一定一样。因为异或运算满足交换律。

我又一次拍案叫绝。

评论已关闭。