LeetCode 137. 只出现一次的数字 II

137. 只出现一次的数字 II

题目：给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
链接 https://leetcode.cn/problems/single-number-ii/

个人思路

1. 统计每个数字出现的次数并保存在字典中，然后循环字典，当遇到值为1的数就返回键

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        Map = {}
        for i in nums:
            Map[i] = Map.get(i,0) + 1
        for key,value in zip(Map.keys(),Map.values()):
            if value == 1:
                return key
        return -1
1
2
3
4
5
6
7
8
9

时间复杂度：O(n)，其中 n 是数组的长度。
空间复杂度：O(n)。哈希映射中包含最多⌊n/3⌋+1 个元素，即需要的空间为 O(n)

2. 找数学关系：sum(nums) == 3a + x , 而3a+3x == sum(set(nums))。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        total = sum(nums)
        a = sum(set(nums))
        return (3 * a - total) // 2
1
2
3
4
5

官方思路

1. 依次确定每一个二进制位
   

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32):
            total = sum((num >> i) & 1 for num in nums)
            if total % 3:
                # Python 这里对于最高位需要特殊判断
                if i == 31:
                    ans -= (1 << i)
                else:
                    ans |= (1 << i)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12

2. 数字电路设计

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a = b = 0
        for num in nums:
            a, b = (~a & b & num) | (a & ~b & ~num), ~a & (b ^ num)
        return b

1
2
3
4
5
6
7

复杂度分析
时间复杂度：O(n)，其中 n 是数组的长度。
空间复杂度：O(1)。

3. 数字电路设计优化

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a = b = 0
        for num in nums:
            b = ~a & (b ^ num)
            a = ~b & (a ^ num)
        return b

1
2
3
4
5
6
7
8

复杂度分析
时间复杂度：O(n)，其中 n 是数组的长度。
空间复杂度：O(1)。

这几个思路都超纲了，建议看官方链接

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/single-number-ii/solution/zhi-chu-xian-yi-ci-de-shu-zi-ii-by-leetc-23t6/

其他思路

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        n=len(nums)
        l,r=0,n-1
        while l<r:
            k=randint(l,r)
            nums[r],nums[k]=nums[k],nums[r]
            i,j=l,r-1
            while i<=j:
                while i<r and nums[i]<=nums[r]:
                    i+=1
                while j>=l and nums[j]>nums[r]:
                    j-=1
                if i<j:
                    nums[i],nums[j]=nums[j],nums[i]
                    i+=1
                    j-=1
            nums[i],nums[r]=nums[r],nums[i]
            if (i-l+1)%3!=0:
                r=i
            else:
                l=i+1
        return nums[l]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

作者：atoi-2
链接：https://leetcode.cn/problems/single-number-ii/solution/python3-kuai-su-xuan-ze-fen-zhi-suan-fa-prk3u/