137.md

137. Single Number II

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/single-number-ii/description/

内容描述

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

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

一行，算出set和的三倍，然后减去总的sum，就是所求数字的2倍

beats 100%

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return int((3 * sum(set(nums)) - sum(nums)) // 2)

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

参考文章：

1. Detailed explanation and generalization of the bitwise operation method for single numbers
2. bron 【中文】简短又通俗的理解
3. leetcode-137-Single Number II-第二种解法

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

beats 87.99%

class Solution:
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        x1, x2, mask = 0, 0, 0
        for num in nums:
            x2 ^= x1 & num
            x1 ^= num
            mask = ~(x1 & x2)
            x2 &= mask
            x1 &= mask
        return x1 # Since p = 1, in binary form p = '01', then p1 = 1, so we should return x1. 
                  # If p = 2, in binary form p = '10', then p2 = 1, and we should return x2.
                  # Or alternatively we can simply return (x1 | x2).