题目链接: 数组中只出现一次的数字
题意: 一个整型数组里除了两个数字之外, 其他的数字都出现了两次. 请写程序找出这两个只出现一次的数字.
题解:
1, 我最开始想到用 map 去统计一下. 第一次出现这个数字后标记这个位置, 再从当前位置向后找第二个出现 1 次的数字.
2, 后面想到用 set, 好像也是差不多..
3, 正解是异或. 出现偶数次的数字, 异或自己肯定是 0. 整个数组异或完肯定是只有那出现一次的两个数的结果. 再找到其中一个数提供 1 这个 bit 位, 就能找到这两个数字.
代码:
- class Solution {
- public:
- void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
- map<int,int> mp;
- int len = data.size();
- for( int i = 0; i <len ;i++){
- mp[data[i]]++;
- }
- int flag;
- for(int i = 0; i < len ;i++){
- if(mp[data[i]]==1){
- *num1 = data[i];
- flag = i;
- break;
- }
- }
- for(int i = flag+1; i < len ;i++){
- if(mp[data[i]]==1){
- *num2 = data[i];
- break;
- }
- }
- }
- };
- OR
- class Solution {
- public:
- void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
- set<int> ss;
- set<int>::iterator it;
- int len = data.size();
- for(int i = 0; i <len ;i++){
- if(ss.find(data[i]) == ss.end())
- ss.insert(data[i]);
- else{
- it = ss.find(data[i]);
- ss.erase(it);
- }
- }
- it = ss.begin();
- *num1 = *it;
- *num2 = *(++it);
- }
- };
- OR
- class Solution {
- public:
- int FindBit(int num){ // 二进制数里第一个为 1 的位数
- int index = 0;
- while((num&1) == 0 && (index < 8*sizeof(int))){
- num = num>>1;
- index++;
- }
- return index;
- }
- // 判断 index 上 bit 位是否为 1
- bool isbit(int num ,int index){
- num = num>>index;
- return (num&1);
- }
- void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
- int len = data.size();
- if(len < 2) return;
- int res = 0; // 数组异或结果
- for(int i = 0; i < len ; i++) res ^= data[i];
- int num = FindBit(res);
- *num1 = 0; *num2 = 0;
- for(int i = 0; i < len; i++){
- if(isbit(data[i],num)) *num1^=data[i];
- else *num2 ^=data[i];
- }
- }
- };
来源: http://www.bubuko.com/infodetail-3447685.html