leetcode137-- Single Number II

leetcode137-- Single Number II

题目

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

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

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

解法

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = b = 0
        for num in nums:
            b = b ^ num & ~a
            a = a ^ num & ~b
        # return a|b
        return b

这个确实有一些妙啊!

解释一下,之前那个解决出现两次的时候用的是按位异或的方法,把出现两次的都消掉了,而这次是只有一个出现了一次,而其他的都是三次,

这时候的想法可以是用两个数来标记状态,比如用数字3来举例

第一次见到3的时候,

b=3, a=0 第二次见到3的时候

b=0,a=3 第三次见到3的时候

b=0,a=0

所以最后返回的b就是只出现一次的那个数字,因为其他的都消掉了

所以是

b=a=0

for num in nums:
    b = (b^num) & (~a)
    a = (a^num) & (~b)

return b

其实这个题的思路也还是源自于上一个题, 上一个题的想法是出现2次的就相互抵消, 所以这个题的想法是出现三次的相互抵消,所以就用了2个指标来进行一个标记.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦