一、题目描述
给你一个整数数组 nums
,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1:
输入:nums = [2,2,3,2]
输出:3
示例 2:
输入:nums = [0,1,0,1,0,1,99]
输出:99
提示:
1 <= nums.length <= 3 * 104
-2^31 <= nums[i] <= 2^31 - 1
nums
中,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次
进阶:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 只出现一次的数字 II( LeetCode 137 ):https://leetcode-cn.com/problems/single-number-ii
class Solution {
public int singleNumber(int[] nums) {
// 设置一个长度为 32 位的数组
// 在这个数组中,每一位存储的就是 nums 数组中每一位二进制形式相加后 1 的个数
int[] cnt = new int[32];
// 遍历 nums 数组
// 虽然这里有两个 for 循环,但是内层循环的 n 是常数,因此时间复杂度依旧为 O(n)
for (int i = 0 ; i < nums.length ; i++ ) {
// 获取第 i 位的数字
int num = nums[i];
// 将 num 展开为二进制的形式,有 32 位
for (int j = 0; j < 32; j++) {
// >> 表示右移符号,右移运算是将一个二进制位的操作数按指定移动的位数向右移动,移出位被丢弃
// >> j 表示右移了 j 位
// 比如 num 的二进制表示为
// 0000 0000 0000 0000 0000 0000 0000 0010
// >> 1 之后变成了
// _000 0000 0000 0000 0000 0000 0000 0001
// _ 在计算机中默认为 0 ,所以结果就是 0000 0000 0000 0000 0000 0000 0000 0001
int temp = num >> j;
// & 表示按位与运算符,只有对应的两个二进位都为 1 时,结果位才为 1
// 每次将 num 向右移动之后,都将移动后的数和 1 进行按位与操作
// 这样就得到了 num 中第 i 个二进制位
// 比如 num 的二进制表示为
// 0000 0000 0000 0000 0000 0000 0000 0010
// 当 j = 0 时,temp 为
// 0000 0000 0000 0000 0000 0000 0000 001【0】 // temp 的二进制表示
// &
// 0000 0000 0000 0000 0000 0000 0000 000【1】 // 1 的二进制表示
// =
// 0000 0000 0000 0000 0000 0000 0000 000【0】 // 等于 0
// 即 num 的第 0 个位置的二进制位 0
// < -------------->
// 当 j = 1 时,temp 为
// 0000 0000 0000 0000 0000 0000 0000 000【1】 // temp 的二进制表示
// &
// 0000 0000 0000 0000 0000 0000 0000 000【1】 // 1 的二进制表示
// =
// 0000 0000 0000 0000 0000 0000 0000 000【1】 // 等于 1
// 即 num 的第 1 个位置的二进制位 1
int x = temp & 1;
// 如果第 j 位的二进制位是 1,把它累加到 cnt[j] 上
// cnt[j] 表示 nums 数组中每一个数字二进制形式表示后,第 j 位有多少个 1
if ( x == 1) {
cnt[j]++;
}
}
}
// 使用 ans 用来记录 nums 中那个只出现了一次的元素
// 一开始 ans 的二进制表示为
// 0000 0000 0000 0000 0000 0000 0000 0000
// 即由 32 个 0 组成
int ans = 0;
// 此时,cnt 已经存储的 nums 数组中每一位二进制形式相加后 1 的个数
// 遍历每个位置
for (int i = 0; i < 32; i++) {
// 因为相同数字的二进制表示是一样的,也就意味着如果它出现了三次,那么这个数字相加三次之后,
// 在某个位置上出现 1 的次数要么是 0 次,要么是 3 次
// 比如数字 2,它的二进制是 0000 0000 0000 0000 0000 0000 0000 00【1】0
// 出现三次时,【1】 也必然出现三次
// 将某个位置相加的结果除以 3,如果余数为 1,表明只出现了一次
int temp = cnt[i] % 3;
// 把出现了一次的二进制位添加到 ans 上
if (temp == 1) {
// << 表示左移符号,用来将一个数的各二进制位全部左移若干位
// 移动的位数由右操作数指定,右操作数必须是非负值,其右边空出的位用 0 填补,高位左移溢出则舍弃该高位
// 这个操作就是不断的填充二进制
int num = 1 << i;
// 把二进制结果累加到 ans 上
ans += num;
}
}
// 返回 ans 就行
return ans;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 只出现一次的数字 II( LeetCode 137 ):https://leetcode-cn.com/problems/single-number-ii
class Solution {
public:
int singleNumber(vector<int>& nums) {
// 设置一个长度为 32 位的数组
// 在这个数组中,每一位存储的就是 nums 数组中每一位二进制形式相加后 1 的个数
vector<int> cnt(32, 0);
// 遍历 nums 数组
// 虽然这里有两个 for 循环,但是内层循环的 n 是常数,因此时间复杂度依旧为 O(n)
for (int i = 0 ; i < nums.size() ; i++ ) {
// 获取第 i 位的数字
int num = nums[i];
// 将 num 展开为二进制的形式,有 32 位
for (int j = 0; j < 32; j++) {
// >> 表示右移符号,右移运算是将一个二进制位的操作数按指定移动的位数向右移动,移出位被丢弃
// >> j 表示右移了 j 位
// 比如 num 的二进制表示为
// 0000 0000 0000 0000 0000 0000 0000 0010
// >> 1 之后变成了
// _000 0000 0000 0000 0000 0000 0000 0001
// _ 在计算机中默认为 0 ,所以结果就是 0000 0000 0000 0000 0000 0000 0000 0001
int temp = num >> j;
// & 表示按位与运算符,只有对应的两个二进位都为 1 时,结果位才为 1
// 每次将 num 向右移动之后,都将移动后的数和 1 进行按位与操作
// 这样就得到了 num 中第 i 个二进制位
// 比如 num 的二进制表示为
// 0000 0000 0000 0000 0000 0000 0000 0010
// 当 j = 0 时,temp 为
// 0000 0000 0000 0000 0000 0000 0000 001【0】 // temp 的二进制表示
// &
// 0000 0000 0000 0000 0000 0000 0000 000【1】 // 1 的二进制表示
// =
// 0000 0000 0000 0000 0000 0000 0000 000【0】 // 等于 0
// 即 num 的第 0 个位置的二进制位 0
// < -------------->
// 当 j = 1 时,temp 为
// 0000 0000 0000 0000 0000 0000 0000 000【1】 // temp 的二进制表示
// &
// 0000 0000 0000 0000 0000 0000 0000 000【1】 // 1 的二进制表示
// =
// 0000 0000 0000 0000 0000 0000 0000 000【1】 // 等于 1
// 即 num 的第 1 个位置的二进制位 1
int x = temp & 1;
// 如果第 j 位的二进制位是 1,把它累加到 cnt[j] 上
// cnt[j] 表示 nums 数组中每一个数字二进制形式表示后,第 j 位有多少个 1
if ( x == 1) {
cnt[j]++;
}
}
}
// 使用 ans 用来记录 nums 中那个只出现了一次的元素
// 一开始 ans 的二进制表示为
// 0000 0000 0000 0000 0000 0000 0000 0000
// 即由 32 个 0 组成
int ans = 0;
// 此时,cnt 已经存储的 nums 数组中每一位二进制形式相加后 1 的个数
// 遍历每个位置
for (int i = 0; i < 32; i++) {
// 因为相同数字的二进制表示是一样的,也就意味着如果它出现了三次,那么这个数字相加三次之后,
// 在某个位置上出现 1 的次数要么是 0 次,要么是 3 次
// 比如数字 2,它的二进制是 0000 0000 0000 0000 0000 0000 0000 00【1】0
// 出现三次时,【1】 也必然出现三次
// 将某个位置相加的结果除以 3,如果余数为 1,表明只出现了一次
int temp = cnt[i] % 3;
// 把出现了一次的二进制位添加到 ans 上
if (temp == 1) {
// << 表示左移符号,用来将一个数的各二进制位全部左移若干位
// 移动的位数由右操作数指定,右操作数必须是非负值,其右边空出的位用 0 填补,高位左移溢出则舍弃该高位
// 这个操作就是不断的填充二进制
int num = 1 << i;
// 把二进制结果累加到 ans 上
ans += num;
}
}
// 返回 ans 就行
return ans;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 只出现一次的数字 II( LeetCode 137 ):https://leetcode-cn.com/problems/single-number-ii
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# 设置一个长度为 32 位的数组
# 在这个数组中,每一位存储的就是 nums 数组中每一位二进制形式相加后 1 的个数
cnt = [0] * 32
# 遍历 nums 数组
# 虽然这里有两个 for 循环,但是内层循环的 n 是常数,因此时间复杂度依旧为 O n)
for i in range(len(nums)) :
# 获取第 i 位的数字
num = nums[i]
# 将 num 展开为二进制的形式,有 32 位
for j in range(32) :
# >> 表示右移符号,右移运算是将一个二进制位的操作数按指定移动的位数向右移动,移出位被丢弃
# >> j 表示右移了 j 位
# 比如 num 的二进制表示为
# 0000 0000 0000 0000 0000 0000 0000 0010
# >> 1 之后变成了
# _000 0000 0000 0000 0000 0000 0000 0001
# _ 在计算机中默认为 0 ,所以结果就是 0000 0000 0000 0000 0000 0000 0000 0001
temp = num >> j
# & 表示按位与运算符,只有对应的两个二进位都为 1 时,结果位才为 1
# 每次将 num 向右移动之后,都将移动后的数和 1 进行按位与操作
# 这样就得到了 num 中第 i 个二进制位
# 比如 num 的二进制表示为
# 0000 0000 0000 0000 0000 0000 0000 0010
# 当 j = 0 时,temp 为
# 0000 0000 0000 0000 0000 0000 0000 001【0】 # temp 的二进制表示
# &
# 0000 0000 0000 0000 0000 0000 0000 000【1】 # 1 的二进制表示
# =
# 0000 0000 0000 0000 0000 0000 0000 000【0】 # 等于 0
# 即 num 的第 0 个位置的二进制位 0
# < -------------->
# 当 j = 1 时,temp 为
# 0000 0000 0000 0000 0000 0000 0000 000【1】 # temp 的二进制表示
# &
# 0000 0000 0000 0000 0000 0000 0000 000【1】 # 1 的二进制表示
# =
# 0000 0000 0000 0000 0000 0000 0000 000【1】 # 等于 1
# 即 num 的第 1 个位置的二进制位 1
x = temp & 1
# 如果第 j 位的二进制位是 1,把它累加到 cnt[j] 上
# cnt[j] 表示 nums 数组中每一个数字二进制形式表示后,第 j 位有多少个 1
if x == 1 :
cnt[j] += 1
# 使用 ans 用来记录 nums 中那个只出现了一次的元素
# 一开始 ans 的二进制表示为
# 0000 0000 0000 0000 0000 0000 0000 0000
# 即由 32 个 0 组成
ans = 0
# 此时,cnt 已经存储的 nums 数组中每一位二进制形式相加后 1 的个数
# 遍历每个位置
for i in range(32) :
# 因为相同数字的二进制表示是一样的,也就意味着如果它出现了三次,那么这个数字相加三次之后,
# 在某个位置上出现 1 的次数要么是 0 次,要么是 3 次
# 比如数字 2,它的二进制是 0000 0000 0000 0000 0000 0000 0000 00【1】0
# 出现三次时,【1】 也必然出现三次
# 将某个位置相加的结果除以 3,如果余数为 1,表明只出现了一次
temp = cnt[i] % 3
# 把出现了一次的二进制位添加到 ans 上
if temp == 1 :
# << 表示左移符号,用来将一个数的各二进制位全部左移若干位
# 移动的位数由右操作数指定,右操作数必须是非负值,其右边空出的位用 0 填补,高位左移溢出则舍弃该高位
# 这个操作就是不断的填充二进制
num = 1 << i
# 把二进制结果累加到 ans 上
ans += num
# 返回 ans 就行
# 在 Python 中需要对最高位进行特殊判断。
return ans if cnt[31] % 3 == 0 else ~(ans ^ 0xffffffff)