只出现一次的数字||| —— 哈希映射、异或位运算+分治思想

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

一、题目描述及思路讲解

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次。那根据统计这个对应元素出现的次数，我们首先可以想到什么？是的，就是哈希映射，这也是我们要讲的第一种方法，是大家比较容易想到的；但有没有更加巧妙的方法呢，没错，就是异或操作，它也可以对两个数进行一个判断比较，而且我们要基于一个分治的思想，“分而治之”地分步去解这道题。
• 想知道怎么用着两种方法求解吗，那就跟我来吧

二、方法罗列及步骤详解

方法一 【哈希映射】

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

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）

其次，这里很关键的一步，我们要去分离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)，虽然比哈希映射来的复杂难懂，但其所使用的空间没有哈希映射所要的多，节省了些许内存空间
  

三、归纳总结与拓展

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

• 这是类似的题型，有兴趣的小伙伴可以去看看
• 136.只出现一次的数字
• 137.只出现一次的数字||
• 619.只出现一次的最大数字