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

数组中只出现一次的数字

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

这道题有一个前置题目,就是将本题的条件改为“一个整型数组里除了一个数字n之外,其他的数字都出现了两次”。

先来解决这道前置题目,可以想到用异或运算解决,出现两次的数字异或之后为0,而0^n = n,所以最后得到的数一定是n。

接下来解决本题。本题有两个数字只出现一次,所以依次异或一遍得到的是两个数字做异或的结果tmp。

我们考虑异或操作是一个位运算,当两个数字的同一位不同时,异或得到该位为1,否则为0。

所以,我们可以从tmp中选出为1的一位,然后将原数组分为两组,第一组为该位为1,第二组为该位为0,这样就能将两个只出现一次的数分到两个数组中,且这两个数组都满足“一个整型数组里除了一个数字n之外,其他的数字都出现了两次”。

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int sum = 0;
        for (auto &i: data) sum ^= i;
        int bt = 0;
        while (((sum >> bt) & 1) == 0) bt++;
        int n1 = 0, n2 = 0;
        for (auto &i: data) {
            if ((i >> bt) & 1) {
                n1 ^= i;
            }
            else {
                n2 ^= i;
            }
        }
        *num1 = n1;
        *num2 = n2;
    }
};

全部评论

相关推荐

码农索隆:这种hr,建议全中国推广
点赞 评论 收藏
分享
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
07-02 13:52
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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