首页 > 代码库 > 【LeetCode】【Python题解】Single NumberII

【LeetCode】【Python题解】Single NumberII

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

Note:

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

本题是一种极其巧妙的做法,参考的别人的,废话不多说,先上代码

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        ones,twos=0,0
        for ele in A:
            ones = ones^ele & ~twos
            twos = twos^ele & ~ones
        return ones

短短几行就可以解决这个看似不太简单的问题。首先需要对位进行操作这没有什么疑议了,关键是一般做法就是将每个数的对应位加起来,再对3取余数,最后将每一位的结果重新组成的数字就是最终只出现一次的(原因也很简单,就不多说了)

这种做法没有那么繁琐,而是非常巧妙的遍历一遍数组,时间复杂度为O(n),而且也没有占用额外的空间。

最关键的两行代码是:

ones = ones^ele & ~twos
twos = twos^ele & ~ones

当ele第一次出现时,因为ones和twos都初始化为0,所以很显然运行这两行代码后ones=ele,twos=0.

在此之后如果ele不再出现,那么很显然这就是只出现一次的数字,ones即为最终结果,如果它第二次出现,ones将会被清零,而twos则会储存下ele的值。

当其第三次出现时,ones和twos都会被清零,就像从未出现过该数字一样。

很神奇吧?!


【LeetCode】【Python题解】Single NumberII