首页 > 代码库 > leetcode-Single Number II-137
leetcode-Single Number II-137
输入一个数组，其中除了一个元素只出现一次外，其余元素都出现3次，找出只出现一次的元素
一个系列http://www.cnblogs.com/0summer/p/5829973.html
位运算。出现3次的元素，二进制位上的0或1也必然有3次，以二进制位为划分，求每个二进制位中1出现的次数，%3得到的就是只出现一次的元素的该二进制位的数
时间：ONlgN，即32*N，空间：O32
注意：对于取二进制位来说，%2和&1在正数时等价，但在负数时不等价；判断是否为奇数正负都等价
同理，n/=2和n>>=1也注意
1 class Solution { 2 public: 3 int singleNumber(vector<int>& nums) { 4 int len=nums.size(); 5 //if(len<3) return 0; 6 int ans=0; 7 int cnt[40]; 8 memset(cnt,0,sizeof(cnt)); 9 for(int i=0;i<32;i++){10 for(int j=0;j<len;j++){11 cnt[i]+=(nums[j]>>i)&1;12 }13 ans|=(cnt[i]%3)<<i;14 }15 return ans;16 }17 };
leetcode-Single Number II-137
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。