带你快速刷完67道剑指offer

这是六则或许对你有些许帮助的信息:

1、阿秀在工作之余开发了一个编程资源网站，目前已经收集了很多不错的学习资源和黑科技（附带下载地址），如你有意欢迎体验以及推荐自己认为不错的资源，众人拾柴火焰高，我为人人，人人为我🔥！

2、👉23年5月份我从字节跳动离职跳槽到某外企期间，为方便自己找工作，增加上岸几率，我自己从0开发了一个互联网中大厂面试真题解析网站，包括两个前端和一个后端。能够定向查看某些公司的某些岗位面试真题，比如我想查一下行业为互联网，公司为字节跳动，考察岗位为后端，考察时间为最近一年之类的面试题有哪些？

网站地址：InterviewGuide大厂面试真题解析网站。点此可以查看该网站的视频介绍：B站视频讲解 如果可以的话求个B站三连，感谢！

3、😊 分享一个学弟发给我的20T网盘资源合集，点此白嫖，主要是各类高清影视、电视剧、音乐、副业、纪录片、英语四六级考试、考研考公等资源。

4、😍免费分享阿秀个人学习计算机以来收集到的免费学习资源，点此白嫖；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏

5、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

6、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行不如一群人报团取暖，圈子里沉淀了很多过去21/22/23届学长学姐的经验和总结，好好跟着走下去的，最后基本都可以拿到不错的offer！此外，每周都会进行精华总结和分享！如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话，可以点此下载 。

No40、数组中只出现一次的数字

牛客网原题链接 (opens new window)

题目描述

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

1、常规做法

void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
    unordered_map<int, int> unmp;
    for (int i = 0; i < data.size(); ++i) {
        unmp[data[i]] += 1;
    }


    auto it = unmp.begin();
    while (it != unmp.end()) {
        if (it->second == 1) {
            *num1 = it->first;
            ++it;
            break;
        }
        ++it;
    }

    while (it != unmp.end()) {
        if (it->second == 1) {
            *num2 = it->first;
            break;
        }
        ++it;
    }
}

二刷：

1、hash表的笨方法

运行时间：3ms 占用内存：376k

void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
    unordered_map<int,int> unmp;
    for(auto a:data){
        unmp[a]++;
    }

    auto beg = unmp.begin();
    while(beg != unmp.end())
    {
        if(beg->second == 1)
        {
            *num1 = beg->first;
            beg++;
            break;
        }
        beg++;

    }

    while(beg != unmp.end())
    {
        if(beg->second == 1)
        {
            *num2 = beg->first;
            break;
        }
        beg++;

    }
}

2、异或做法，很棒

当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。

依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。

运行时间：3ms 占用内存：376k

void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {


    if (data.size() < 2) return;

    int totalNum = 0;
    for (int i = 0; i < data.size(); i++) {
        totalNum ^= data[i];//所有数异或，结果为不同的两个数字的异或
    }

    int sign = 0;//标志位，记录totalNum中的第一个1出现的位置
    for (; sign < data.size(); sign++) {
        if ((totalNum & (1 << sign)) != 0) { //左移 sign 位，将所有数字进行左移sign位，而低位补上0
            break;
        }
    }
    cout << sign << endl;
    num1[0] = 0;
    num2[0] = 0;
    for (int i = 0; i < data.size(); i++) {
        if ((data[i] & (1 << sign)) == 0) {//标志位为0的为一组，异或后必得到一个数字（这里注意==的优先级高于&，需在前面加（））
            num1[0] ^= data[i];
            cout << "0 "<<data[i] << " " << (1<<sign) << endl;
        }
        else {
            num2[0] ^= data[i];//标志位为1的为一组
            cout << "1 " << data[i] << " " << (1 << sign) << endl;
        }
    }
    cout << num1[0] << num2[0] << endl;       
}