首页 > 代码库 > leetcode[137] Single Number II
leetcode[137] Single Number II
题目和上题类似，这里给的数组仅有一个数出现一次，其他的出现3次。返回那个出现一次的数。
这题还是比较难想到的。不想上一题只要异或一下就可以了，不用额外操作。
法一：还是用map方法
class Solution {public:int singleNumber(int A[], int n){ unordered_map<int , int> umap; for (int i = 0; i < n; i++) { umap[A[i]]++; } for (int i = 0; i < n; i++) { if (umap[A[i]] == 1) return A[i]; }}};
法二：还是利用位运算才有办法实现不用额外空间，就是遍历32次每次记录某位的出现的次数，如果不能被三整除，说明那个出现一次的就在该位有值，那么ans 或该位一下就可以了。
int singleNumber(int A[], int n){ int ans = 0; for (int i = 0; i < 32; i++) { int cnt = 0, bit = 1 << i; for (int j = 0; j < n; j++) { if (A[j] & bit) cnt++; } if (cnt % 3 != 0) ans |= bit; } return ans;}
法三：还是位运算，这里利用二进制模拟a进制的方法。对于此题，a为3.
点这里分析和拓展的很好：
对于除出现一次之外的所有的整数，其二进制表示中每一位1出现的次数是3的整数倍，将所有这些1清零，剩下的就是最终的数。用ones记录到当前计算的变量为止，二进制1出现“1次”（mod 3 之后的 1）的数位。用twos记录到当前计算的变量为止，二进制1出现“2次”（mod 3 之后的 2）的数位。当ones和twos中的某一位同时为1时表示二进制1出现3次，此时需要清零。即用二进制模拟三进制计算。最终ones记录的是最终结果。
int singleNumber(int A[], int n) { int ones = 0, twos = 0, xthrees = 0; for(int i = 0; i < n; ++i) { twos |= (ones & A[i]); ones ^= A[i]; xthrees = ~(ones & twos); ones &= xthrees; twos &= xthrees; } return ones;}
该文的拓展很值得学习！
leetcode[137] Single Number II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。