【剑指offer】数组中只出现一次的数字总结

虾米哥 阅读:375 2022-03-12 16:24:49 评论:0
本文章主要介绍了【剑指offer】数组中只出现一次的数字,具有不错的的参考价值,希望对您有所帮助,如解说有误或未考虑完全的地方,请您留言指出,谢谢!

数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路

我们知道两个相同的数字异或的结果为0,所以如果只有一个出现一次的数字,就可以让所有的数字进行异或,那么最后得到的数字就是只出现一次的数字。

现在问题变成了有两个数字,同样我们可以让所有数字异或,最终的结果是两个只出现一次的数字的异或的结果。我们可以找到这个结果的二进制位上为1的下标,例如异或的结果为4,那么对应到二进制上是100,所以在第三位上着两个数字不相同,一个为1,一个为0,所以我们可以以二进制中第三位为区分标准,把数组划分成两份,二进制的第三位为1和为0。

当得到两个小组后,我们知道这两个只出现一次的数已经被分开了,这样就回到最原始的问题上了,问题迎刃而解。代码如下。

代码

#include <iostream> 
#include <vector> 
using namespace std; 
 
void FindNumsAppearOnce(vector<int> data,int num1,int num2); 
int FindFirstOneBit(int target); 
bool isOneBit(int target, int index); 
 
void FindNumsAppearOnce(vector<int> data,int num1,int num2) { 
    if (data.size() < 2) 
        return; 
    int res = data[0]; 
    for(int i=1;i<data.size();i++) 
        res ^= data[i]; 
    int first = FindFirstOneBit(res); 
    num1 = num2 = 0; 
    for (int i = 0; i < data.size(); ++i) { 
        if(isOneBit(data[i], first-1)) 
            num1 ^= data[i]; 
        else 
            num2 ^= data[i]; 
    } 
 
    cout << num1<<endl; 
    cout<<num2 <<endl; 
} 
 
int FindFirstOneBit(int target) { 
    int ret = 0; 
    while((target ^ 1) == 0 && ret < 8* sizeof(int)) { 
        target = target >> 1; 
        ret++; 
    } 
    return ret; 
} 
 
bool isOneBit(int target, int index) { 
    target = target >> index; 
    return target & 1; 
} 
 
 
int main() { 
 
    vector<int> data = {1,1,2,2,3,4,3,5}; 
    FindNumsAppearOnce(data, 0, 0); 
    return 0; 
} 

结果

5

4


标签:加密算法
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

我的关注

全民解析

搜索
关注我们