题解 | #数组中只出现一次的数字#

数组中只出现一次的数字

http://www.nowcoder.com/practice/e02fdb54d7524710a7d664d082bb7811

hash思路
map<int, int>用于记录元素和元素出现的次数
最后过滤出出现一次的两个元素

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int * arr[2] = {num1, num2};
        map<int, int> m;
        for(int i=0; i<data.size(); ++i)
            m[data[i]]++;
        int j = 0;
        for(map<int, int>::iterator it=m.begin(); it!=m.end(); ++it)
            if(it->second == 1)
                *arr[j++] = it->first;
    }
};

位运算

求出所有元素异或的值
拿出最右的1bit位
让所有与上一步的1bit位都是1元素的异或在一起,就得到其中一个数
然后这个数异或一下所有异或在一起的元素值就得到第二个数

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {

        int xor_ = 0;
        for(int i=0; i<data.size(); ++i)
            xor_ ^= data[i];

        //求xor最右边的1bit位
        int right_1 = xor_&(~xor_+1);
        *num1 = 0;
        for(int i=0; i<data.size(); ++i){
            if(data[i]&right_1)
                *num1 ^= data[i];
        }
        *num2 = xor_^ *num1;
    }
};
全部评论

相关推荐

湫湫湫不会java:1.在校经历全删了2.。这些荣誉其实也没啥用只能说,要的是好的开发者不是好好学生3.项目五六点就行了,一个亮点一俩行,xxx技术解决,xxx问题带来xxx提升。第一页学历不行,然后啥有价值的信息也没有,到第二页看到项目了,第一个项目九点,第二个项目像凑数的俩点。总体给人又臭又长,一起加油吧兄弟
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务