写点什么

力扣 260 - 只出现一次的数字||| 【哈希映射、异或位运算 + 分治思想】

作者:Fire_Shield
  • 2022 年 9 月 10 日
    浙江
  • 本文字数:3221 字

    阅读完需:约 11 分钟

力扣260 - 只出现一次的数字||| 【哈希映射、异或位运算+分治思想】

哈喽大家好,本次要讲解的题目是对应力扣上 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:



发布于: 刚刚阅读数: 5
用户头像

Fire_Shield

关注

语言观决定世界观 2022.09.02 加入

高校学生,热爱编程,喜欢写作

评论

发布
暂无评论
力扣260 - 只出现一次的数字||| 【哈希映射、异或位运算+分治思想】_位运算_Fire_Shield_InfoQ写作社区