剑指 Offer II 004. 只出现一次的数字
题目描述
给你一个整数数组 nums
,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1:
输入:nums = [2,2,3,2] 输出:3
示例 2:
输入:nums = [0,1,0,1,0,1,100] 输出:100
提示:
1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums
中,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次
进阶:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
注意:本题与主站 137 题相同:https://leetcode.cn/problems/single-number-ii/
解法
方法一:位运算
我们可以统计所有数字中每个位上出现的 $1$ 的个数,然后对 $3$ 取模。如果某一位上的出现的 $1$ 的个数无法被 $3$ 整除,说明只出现一次的数字在该位上是 $1$,否则是 $0$。
时间复杂度 $O(n \times \log M)$,其中 $n$ 是数组 $nums$ 的长度,而 $M$ 是数组中元素的最大值。空间复杂度 $O(1)$。
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|