数组中唯一只出现一次的数字
题目 数组中唯一只出现一次的数字
思路分析
状态机 构造状态 遇见1变下一个状态 遇见0自环
至于遇见1做什么操作 能实现状态只有三个 就……emmm
这种方法太难了 跳过吧
详解见力扣 这玩意y总也讲的不清楚 不给推出过程 只套一遍代码流程
需要的状态转移方式是，如果出现两个1就抵消为0，用一个变量和异或运算即可实现，而本题是需要1出现三次时才会抵消，因此有三种状态，即1出现的次数为3k, 3k + 1, 3k + 2次
逐个位来看，要设计一个两位的状态转移，出现三个1时，循环抵消，出现0时不变，一个变量只能记录两种状态，因此要用两个变量来记录状态，用one和two两个变量来记录1出现次数 00表示1出现3k次，01表示1出现3k + 1次，10表示1出现3k + 2次
真值表
先看one的状态转移方程 & ~two & x) | (one & ~two & ~x)
= ~two & ((~one & x) | (one & ~x))
= ~two & (one ^ x)
同理，再用转移后的one来求two的状态转移方程
这里，one为当且仅当1出现次数为3k + 1, tow为当且仅当1出现次数为3k + 2 因此如果题目改为，有一个数出现了两次，则返回two即可
或者用第二种方式 遍历统计 好理解些（至于为什么能这样……还是不知道）
考虑数字的二进制形式，对于出现三次的数字，各 二进制位 出现的次数都是 3 的倍数。 因此，统计所有数字的各二进制位中 1 的出现次数，并对 3 求余，结果则为只出现一次的数字。（还是不懂为什么可以这样 但是方法懂了）
代码实现
状态机
class Solution {
public:
int findNumberAppearingOnce(vector<int>& nums) {
int
for(auto x:nums)
{
two=(two^x)&~one;
}
return one;
}
};
遍历统计
class Solution {
public:
int findNumberAppearingOnce(vector<int>& nums) {
//建立一个长度为 32 的数组 counts 记录所有数字的各二进制位的 1 的出现次数。
vector<int> counts(32, 0);
for(int num : nums) {
for(int j = 0; j < 32; j++) {
counts[j] += num & 1;// 更新第 j 位 直接+=即可 是0的话也等于没加
num >>= 1;
}
}
int res = 0, m = 3;
//将counts 各元素对 3 求余，则结果为 “只出现一次的数字” 的各二进制位。
//将counts数组中各二进位的值恢复到数字 resresres 上
//(循环区间是 i∈[0,31])
for(int i = 0; i < 32; i++) {
res <<= 1;
res |= counts[31 - i] % m;
}
return res;
}
};
//只需要修改求余数值m，即可实现解决除了一个数字以外，其余数字都出现m次的通用问题。
同类题型
视频讲解
⬅️ 数组中只出现一次的两个数字 🏠 00-刷题理模型 ➡️ 进制
💬 评论