[Leetcode][python]Single Number/Single Number II

小鱼儿 2022-06-04 23:43 109阅读 0赞

# Single Number #

## 题目大意 ##

一个数组中除了一个数字出现过一次外，其余的数字都出现了两次，找出那个只出现一次的数字。  
注意点：  
算法时间杂度要求为O(n)  
空间复杂度为O(1)

## 解题思路 ##

参考：[http://www.cnblogs.com/zuoyuan/p/3719584.html][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。问题解决。

## 代码 ##

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][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。

## 代码 ##

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

# 总结 #

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

[http_www.cnblogs.com_zuoyuan_p_3719584.html]: http://www.cnblogs.com/zuoyuan/p/3719584.html
[http_www.cnblogs.com_zuoyuan_p_3719753.html]: http://www.cnblogs.com/zuoyuan/p/3719753.html