AlgoPressAppearance
56-II-数组中数字出现的次数II
题目描述
https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1：
输入：nums = [3,4,3,3]
输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1
限制：
- 1 <= nums.length <= 10000
- 1 <= nums[i] < 2^31
思路分析
- hash表记录次数法，不赘述
其他数字都出现了3次，那么这个数字的每个二进制位一定也是3个1或者3个0，就一定能被3整除，举例
3 = 0011 3 = 0011 3 = 0011 5 = 0101
将每一位对3取余，就得到最后的记过 0101 即答案5.
实现代码
csharp
public class Solution {
int[] arr = new int[32];
private void calcBits(int num){
int index = 31;
while(num > 0){
if( (num & 1) == 1){
arr[index]++;
arr[index] %=3;
}
num = num >> 1;
index--;
}
}
public int SingleNumber(int[] nums) {
for(int i=0; i<nums.Length; i++){
calcBits(nums[i]);
}
//计算最后结果
int num = 0;
int multi = 1;
for(int i=arr.Length-1; i>=0; i--){
if(arr[i] == 1){
num+= multi;
}
multi*=2;
}
return num;
}
}
本题可以用自动状态机加速 参考：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/mian-shi-ti-56-ii-shu-zu-zhong-shu-zi-chu-xian-d-4/
实现代码2
csharp
public class Solution{
public int SingleNumber(int[] nums) {
int ones = 0, twos = 0;
for(int i=0; i<nums.Length; i++){
ones = ones ^ nums[i] & ~twos;
twos = twos ^ nums[i] & ~ones;
}
return ones;
}
}