首页 > 代码库 > leetcode-Single Number III-260
leetcode-Single Number III-260
输入一个数组，其中除了两个数只出现一次外，其余的数均出现两次，找出只出现一次的数
一个系列http://www.cnblogs.com/0summer/p/5830714.html
这类题都可用multiset来做，时间ON，不过空间也是ON
既然题目要求空间O1，说明肯定有规律
本题同样位运算，设结果为a,b
1.全部异或得到x
2.x肯定就是只出现一次的两个数的异或，而且二进制位为1的就是这两个数在二进制上不一样的
3.随便找一个x中二进制位为1的，将数组分为两部分，则a,b肯定在不同的两组，问题就转换成了一个数组中只有一个数出现一次，其余出现两次，所以两组内异或得到a,b
1 class Solution { 2 public: 3 vector<int> singleNumber(vector<int>& nums) { 4 int len=nums.size(); 5 vector<int> v; 6 if(len<2) return v; 7 int tmp=0; 8 for(int i=0;i<len;i++) tmp^=nums[i]; 9 int cur=tmp;10 int cnt=0;11 while(cur){12 cnt++;13 int a=cur%2;14 if(a) break;15 cur/=2;16 }17 int one=0,two=0;18 int k=pow(2,cnt-1);19 for(int i=0;i<len;i++){20 if(nums[i]&k) one^=nums[i];21 else two^=nums[i];22 }23 v.push_back(one);24 v.push_back(two);25 return v;26 }27 };
leetcode-Single Number III-260
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。