[LeetCode]136,137,260-只出现一次的数字

136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例:
输入: [2,2,1] -> 输出: 1
输入: [4,1,2,1,2] -> 输出: 4

解法1

常规思路, 找出只出现一次的那个数字.

class Solution:
    def singleNumber(self, nums):
        dic = {}
        for i in nums:
            if i in dic:
                dic.pop(i)
            else:
                dic[i] = 0
        return list(dic)[0]

解法2

将数组中的数逐个异或, 相同的数字会两两抵消, 最终得出的就是只出现一次的数字.

class Solution:
    def singleNumber(self, nums):
       res = 0
        for i in nums:
            res ^= i
        return res

137. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
示例:
输入: [2,2,3,2] -> 输出: 3
输入: [0,1,0,1,0,1,99] -> 输出: 99

解法1

将数组排序后隔3位比较一次与相邻的数是否相同, 如果不相同则是只出现一次的数.
此解法也也可用于136这一题.

class Solution:
    def singleNumber(self, nums):
        nums.sort()
        for i in range(1, len(nums)-1, 3):
            if nums[i-1] != nums[i]:
                return nums[i-1]
        return nums[len(nums)-1]

解法2

纯数学算法将出现一次的数算出来.
此解法同样可以用于136这一题.

class Solution:
    def singleNumber(self, nums):
        return (3*sum(set(nums)) - sum(nums))//2

解法3

用异或和与运算来解决.

class Solution:
    def singleNumber(self, nums):
        ones = 0
        twos = 0
        threes = 0
        for i in nums:
            twos |= ones&i #当前的数和出现一次的数进行与运算, 得出出现两次的数
            ones ^= i #保持ones中只含有出现一次的数
            threes = ones & twos #出现两次的数和出现一次的数进行与运算, 得出出现3次的数
            ones &= ~threes #从出现一次的数中除去出现3次的数
            twos &= ~threes #从出现两次的数中除去出现3次的数
        return ones

260. 只出现一次的数字 III
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例:
输入: [1,2,1,3,2,5] -> 输出: [3,5]

解法1

巧用用异或和与运算来获得两个数字.

class Solution:
    def singleNumber(self, nums):
        a = 0
        for i in nums:
            a ^= i  #逐个数字进行异或运算, 最后得出两个不同数字的异或运算结果
        a &= -a
        res = [0, 0]
        for i in nums:
            if i&a == 0:
                res[0] ^= i
            else:
                res[1] ^= i
        return res

解法2

运用collections库.
此解法同样可用于上两题.

class Solution:
    def singleNumber(self, nums):
        dic = collections.Counter(nums)
        return [key for key,value in dic.items() if value == 1]