题目描述

[EN | CN]

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

说明:

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

示例 1:

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

示例 2:

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

解法 1:暴力法

与《LeetCode 136. 只出现一次的数字 ⌨️》的解法 1 类似,tong统计每个元素出现的次数,最后返回那个只出现 1 次的元素。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(n)$,额外空间存储。

实现与结果如下:

1
2
3
4
5
6
7
from collections import Counter
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count = Counter(nums)
        for num, c in count.items():
            if c % 3 == 1:
                return num
  • 执行用时:36 ms,在所有 Python3 提交中击败了 96.14% 的用户。
  • 内存消耗:15 MB,在所有 Python3 提交中击败了 5.88% 的用户。

解法 2:与集合求和的倍数做差

与《LeetCode 136. 只出现一次的数字 ⌨️》的解法 2 类似,我们将数组转为集合然后求和,再用和的 3 倍减去数组的和,得到的结果再除以 2 就是只出现一次的元素。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(n)$,额外空间存储。

实现与结果如下:

1
2
3
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return (sum(set(nums)) * 3 - sum(nums)) // 2
  • 执行用时:36 ms,在所有 Python3 提交中击败了 96.14% 的用户。
  • 内存消耗:15.2 MB,在所有 Python3 提交中击败了 5.88% 的用户。

解法 3:按位统计

与《LeetCode 136. 只出现一次的数字 ⌨️》的解法 4 基本一样。

假设数组长度为 $n$,最长的数字的长度是 $m$,那么

  • 时间复杂度为 $O(mn)$,需要遍历一遍;
  • 空间复杂度为 $O(1)$,只需要保存一个数。

实现与结果略。