蛮三刀酱的博客

技术公众号:后端技术漫谈

【Leetcode】【python】Single Number Single Number II

发表于 更新于 分类于 阅读次数： Valine：

Single Number

题目大意

一个数组中除了一个数字出现过一次外，其余的数字都出现了两次，找出那个只出现一次的数字。
注意点：

算法时间杂度要求为O(n)
空间复杂度为O(1)

解题思路

参考：http://www.cnblogs.com/zuoyuan/p/3719584.html
这题考的是位操作。只需要使用异或(xor)操作就可以解决问题。异或操作的定义为：x ^ 0 = x; x ^ x = 0。用在这道题里面就是：y ^ x ^ x = y; x ^ x = 0; 举个例子：序列为：1122334556677。4是那个唯一的数，之前的数异或操作都清零了，之后的数：4 ^ 5 ^ 5 ^ 6 ^ 6 ^ 7 ^ 7 = 4 ^ ( 5 ^ 5 ^ 6 ^ 6 ^ 7 ^ 7 ) = 4 ^ 0 = 4。问题解决。

代码

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = nums[0]
        for i in nums[1:]:
            result ^= i
            # print result
        return result

Single Number II

题目大意

一组数字中，有一个数字只出现一次，其余的都出现了三次，找出只出现了一次的那个数字。
注意点：
线性时间复杂度
最好不用额外申请空间

解题思路

参考：http://www.cnblogs.com/zuoyuan/p/3719753.html
这道题就比较难了。也是考察位操作。网上的位操作解法看了好半天也没有得其精髓。由于序列中除了那唯一的一个数之外所有的数都是三个三个出现的。如果把这些数都转换成二进制，那么二进制数中1的那些位会连续出现三次，我们可以利用这个思路来解题。比如：3331222转换成二进制为：11 11 11 01 10 10 10。在第1位上，1出现了4次。第2位上，1出现了6次。那么我们把每一位上为1的个数mod 3剩下的1就是我们所求的数，比如这个例子：4 mod 3 = 1; 6 mod 3 = 0。这样剩下的二进制位为：01。那最后所求的数就是1了。

那怎么实现这个想法呢？使用二进制模拟三进制。在连续来3个1后清0。使用两个bit位，bit1和bit2。初始状态bit1和bit2都是0，即00，在来了第一个1后，变成了01，来了第二个1后变成了10，来了第三个1后，变成了11，然后清0为00，即：00->01->10->11，然后将11清为00，这个过程就是我们编程的思路。比如如果输入序列为：1 1 1 1 1 1 1，则变化过程为：00->01->10->11->00->01->10->11->00->01，最后剩下的是1，也就得到了结果。如果位数多那么以此类推，比如序列为：3 3 3 2 2 2 1。则二进制为：11 11 11 10 10 10 01。则低位为1 1 1 0 0 0 1，变化过程为：00->01->10->11->00->00->00->00->01，所以低位剩下1。高位为：1 1 1 1 1 1 0，变化过程为：00->01->10->11->00->01->10->11->00->00，所以高位剩下0。那么最后剩下的是01，也就是1。如果位数更多，可以以此类推。程序中的one相当于bit1，two相当于bit2。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        one = 0; two = 0; three = 0
        for i in range(len(nums)):
            # print one, two, three
            two |= nums[i] & one  # two为1时，不管A[i]为什么，two都为1
            # print two
            one = nums[i] ^ one  # 异或操作，都是1就进位
            # print one
            three = ~(one & two) # 以下三步的意思是：如果one和two都为1时，就清0，反之则保持原来状态。
            one &= three
            two &= three
            # print one, two, three
            # print '----'
        return one

总结

第二题可以输出二进制理解