美文网首页
137. 只出现一次的数字 II-leetcode

137. 只出现一次的数字 II-leetcode

作者: 佛祖拿屠刀 | 来源:发表于2018-12-24 23:23 被阅读0次

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,3,2]
输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

这个和136的题有点像,但是这里要求是重复出现的次数是3

这时候就需要两个数来记录

第一次num:

a = 0,b=0
b = ~a&(b^num) =num 
a = ~b&(a^num) = 0

第二次num:

a=0,b=num
b = ~a&(b^num) =0
a = ~b&(a^num) =num

第三次num:

a=num,b=0
b = ~a&(b^num) =0
a = ~b&(a^num) =0

这样出现三次的数字就会置零,出现一次的数字就会在b里面体现

所以答案是

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var a = 0,b = 0
        for num in nums {
            b = ~a & (b ^ num)
           a = ~b & (a ^ num)
        }
    
        return b
    }
}

相关文章

网友评论

      本文标题:137. 只出现一次的数字 II-leetcode

      本文链接:https://www.haomeiwen.com/subject/dvgtlqtx.html