哈喽大家好，本次要讲解的题目是对应力扣上 260. 只出现一次的数字 III，本文将用两种方法来解决这道==面试高频题==

@TOC

一、题目描述及思路讲解

1. 题目描述

力扣原题链接

• 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案

• 进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

• 示例 1： 输入：nums = [1,2,1,3,2,5] 输出：[3,5] 解释：[5, 3] 也是有效的答案。

示例 2： 输入：nums = [-1,0] 输出：[-1,0]

示例 3： 输入：nums = [0,1] 输出：[1,0]

2. 思路顺理

• 首先我们从题目要求中可以看到，它需要找的是在 nums 数组中只出现过一次的两个元素，从事例 1 中可以看出，[1,2,1,3,2,5]这个数组中 1 和 2 都出现了两次，唯有 3 和 5 只出现了 1 次。那根据统计这个对应元素出现的次数，我们首先可以想到什么？是的，就是==哈希映射==，这也是我们要讲的第一种方法，是大家比较容易想到的；但有没有更加巧妙的方法呢，没错，就是==异或操作==，它也可以对两个数进行一个判断比较，而且我们要基于一个分治的思想，“分而治之”地分步去解这道题。

• 想知道怎么用着两种方法求解吗，那就跟我来吧:racehorse:

二、方法罗列及步骤详解

方法一 【哈希映射】

哈希的代码量不多，因此直接来:point_down:

class Solution {public:    vector<int> singleNumber(vector<int>& nums) {        unordered_map<int,int> count;        for(auto& i : nums)        {            count[i]++;        }                stack<int> s;        vector<int> result;        for(auto& i : count)        {            if(i.second == 1)            {                s.push(i.first);            }        }
        //不做这一步也ok,反过来也是正确答案，加深一下对堆栈的结构        while(!s.empty())        {            result.push_back(s.top());               s.pop();              }        return result;    }};

详细讲解：

• 好，我们来详细讲解一下，首先就是哈希映射的定义 unordered_map<key,value>,这里 key 呢，你可以放需要操作的元素，也就是题目中给到的数组元素，而这里的 value 呢，则相当于它所对应的数所出现的次数，接着，就是利用循环去遍历其中的元素，这里的auto& 表明的是引用变量，当然你也可以写成 for 循环用 i 去遍历，这都可以，auto 显的清晰又简洁一些

• 利用完循环累加每个元素的个数后，我们就要去判断这个次数是否为 1，因此上面是==auto& i : nums==，对题目本身给出的数组的一个遍历，下面是==auto& i : count==，对我们构建的哈希映射的一个遍历，我们去判断其 second 值是否== 1，如果是就将其 first 值放入我们所开辟的 stack 堆栈，这里的 first 和 second 是什么意思呢？这就代表的是映射中的 key 值和 value 值，利用 first 和 second 我们便可以拿到其对应的内容

• 最后呢，是一个从将元素逆序的这么一个操作因为题目中讲了，对于[3,5]，[5, 3] 也是有效的答案。因此不作这一步操作也是 ok 的，那你只要开辟一个 vector 数组容器，然后将 i.first 值放入即可，这里是利用里一个堆栈的先进后出的思想，去逆序打印数组

• 哈希映射的时间复杂度是和空间复杂度均为 O(n)，那我们便开始思考，有没有空间复杂度均为 O(1)的算法呢？

• 
  
  

方法二 【异或位运算+分治思想】

看完了哈希，我们又想到了一种更加巧妙的方法，那就是异或运算，首先，我们利用分治的思想将其降维分为三步，逐一求解，我们知道异或的原理就是两数异或相同取 0，不同取 1，然后一个数和 0 异或始终都是这个数本身。知道了这些，就可以开始接下里的一步步操作了，我们的最终目的就是将这两个数分开然后再合并起来

第一步

首先用一个变量，初始化为 0，将其与题目给到的数组中每一个数进行一个异或操作，因为出现两次的数异或之后一样变为 0 了，所以最终得到的就是得到那两个只出现一次的数。

    int ret = 0;    for(int i = 0;i < nums.size();++i)    {        //先对所有元素进行异或操作，消除相同元素，找出两个不同的数        ret ^= nums[i];    }

第二步 （Important）

其次，这里很关键的一步:elephant:，我们要去分离 x1 和 x2，接下来用画图进行一个细致地讲解，在这里，我们假设这个 x1 是 3，x2 是 5，因为在内存中，一个字节对应的是 8 个位，来看到最后八个位，两数异或后的结果是 110，根据相同取 0，不同取 1 的原则，如果两个位异或后为 1，说明一定是一个为 1，一个为 0，因为我们将这两个数分为两组，第 pos 位为 1 的为 1 组，第 pos 位为 0 的为 1 组，这就是所谓的异或位运算

    //判断ret数组中的第pos位为1的     int pos = 0;     while(pos < 32)     {         if(ret & (1<<pos))             break;         else             ++pos;     }   

详细讲解：

• 这里为什么要判断到 pos < 32 呢，因为整型是 4 个字节，1 个字节 8 位，那 4 个字节就是 32 位，我们要去遍历判断其所有位数。这里的"&"符号就是按位与的意思，只有同时为真，表达式才为真，只要有一方为假，便不会成立，这里的按位与 &和逻辑与 && 不一样，如果是逻辑与，判断了第一个为 false 之后便不会再判断第二个表达式，具体的大家可以去了解一下，就不详解

• 这里我们主要是讲这个==1<<m==，这个移位操作，在 c 语言里我们就学过了这个移位操作，"<<2"就是往左两位，也就是除 2，">>2"就是往右移两位，也就是乘 2，但不要和“cin>>，cout<<”这两个输入输出流混淆。

• 在一位一位向后遍历判断的过程中，因为上一步异或完得到的 x1,x2 一定不相等，所以 ret 一定为 1，所以我们只要看 1<<pos 即可，拿 1 左移 pos 位，与 ret 相与，如果还是 0，表示表示这两个数字在这一位上相同，依旧向后遍历，做++pos 的操作，但是如果与完之后为 1 了，表示这两个数字在这一位上不同，只要是有一位不同，程序就 break 退出，这个判断最多从 0 走到 31 位，总能找到 1，因为此时已经找到了不同的数，将进行下一步对他们进行分组

• 

第三步

最后，我们就要将分离出来的两个不同的数进行一个分组，为 0 的保存进一个变量，为 1 的保存进另一个变量，通过这样，其实就展现了分治的思想，将问题简化为“这个数组每个数字都出现了两次，有一个数字出现了一次，求出改数字”，那我们就分别对其进行求解，最后放进一个 vector 容器即可

    //将两个只出现一个的数分组存放    int x1 = 0;    int x2 = 0;     for(int i = 0;i < nums.size();++i)    {        if(nums[i] & (1<<pos))            x1 ^= nums[i];        else            x2 ^= nums[i];    }        
     vector<int> result(2);     result[0] = x1;     result[1] = x2;          return result;

详细讲解：

• 代码中可以看到，首先定义了两个变量用来存放将数组中的不同的两个数，然后进行判断，也是一样将 nums 数组中的值和 1<<pos 相与，一个数和 1 左移 pos 位就可以判断它的第 pos 为是否为 1，如果为 1，则存入 x1 中，不为 1 则存入 x2 中，这个没关系，任意存入哪一个都可以，只要将它们分来即可，最后动态开辟一个 vector 数组容器，然后将两个数放入并输出即可，这样就完成了这道题的求解，代码便是三部分的组合，最后是这道题最后的通过界面，看完讲解之后你也可以再去做一做，看看自己能能不能一步步分析出来，异或位运算的时间复杂度是 O(n),空间复杂度是 O(1)，虽然比哈希映射来的复杂难懂，但其所使用的空间没有哈希映射所要的多，节省了些许内存空间

• 

三、归纳总结与拓展

这就是我要带给你们的这道力扣题的讲解，这道题虽说只是中等难度的题，但其在各大厂的面试中出现的频率还是蛮高的，试想如果你能想到异或的这种思维，是否会显得出彩一些呢，虽然是比较难理解，但自己多去琢磨一下画画图，也就没那么难了。最后欢迎大家在评论区留言或者私信我都可以，谢谢您的观看:cherry_blossom:

• 这是类似的题型，有兴趣的小伙伴可以去看看

• 136.只出现一次的数字
  

• 137.只出现一次的数字||
  

• 619.只出现一次的最大数字