本文最后更新于 354 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
给你一个整数数组 nums
,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
示例 1:
输入:nums = [2,2,3,2]
输出:3
示例 2:
输入:nums = [0,1,0,1,0,1,99]
输出:99
提示:
1 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
nums
中,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次
解法一:位运算
算法思路:
由于数组中的元素都在 int(即 32 位整数)范围内,因此我们可以依次计算答案的每一个二进制位是 0 还是 1。
具体的,对于出现三次的数字,各二进制位出现的次数都是 3 的倍数,因此,统计所有数字的各二进制位中 1 的出现次数,并对 3 求余,结果则为只出现一次的数字。
代码实现:
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for(int i = 0; i < 32; i++){
int cnt = 0;
for(int num : nums){
cnt += num >> i & 1;
}
cnt %= 3;
ans |= cnt << i;
}
return ans;
}
}
复杂度分析:
时间复杂度: O(nlogC),其中 n 为数组 nums 的长度,C 是元素的数据范围。
空间复杂度: O(1)。