异或在笔试题中的超神表现 超级码力在线编程大赛初赛 第2场 T1-T4题解 1397D. Stoned Game(博弈) Codeforces Round #666(Div.2)A~D题题解 高性能微服务架构技术选型 阿里饿了么Java4面:(数据结构+框架源码+JVM+分布式) 2020java面试总结 使用ffmpeg提取mp4内部日期重命名文件(需lua) 【剑指Offer】56.2 数组中只出现一次的数字,其他出现3次 JAVA二三事-使用IO+Properties实现动态读取文本信息 排序算法的C语言实现C代码(未更完) RT-Thread 内核学习--信号量的初步使用 【剑指Offer】57.2 和为S的连续正数序列 Qt三方库开发技术:QXlsx介绍、编译和使用 4G DTU模块的作用和功能说明 【Tips】- Wifi模块和4G无线通信 【5G核心网】 Identifiers 身份标识 DPDK支持的硬件:CPU、网卡NIC、加密引擎、基带加速器 如何根据普通ip地址获取当前地理位置 人工智能能力提升指导总结 520了,用32做个简单的小程序 程序员的数学--用贝叶斯定理来推断一个案子 文旅部新规:在线旅游网站不得擅自屏蔽删除评价 不得大数据杀熟 苏宁易购开学季消费大数据:手机以旧换新销量增长299% 做实供电服务“133” 助大数据直上“云”端 思科前程序员离职 5 月后“删虚拟机跑路”,240 万美元打水漂,网友:够狠! 抗疫代码成国博最新藏品 阿里程序员“写代码写进国博挺酷” 国博史上首次收藏代码!它们是阿里程序员写下的抗疫代码 威胜信息发布2020年上半年业绩:物联网产业进入爆发期 营收净利双增长 下月发布会不止有新品折叠屏手机 酷开的物联网家居生态野心初现 史上最全的数据库面试题 数据库面试必看 一个数据库SQL查询的数次轮回 百度智能云正式对外发布百度智能云数据库品牌GaiaDB 数据库三大泛式是什么 电力行业网管需求 IT运维管理解决方案 citrix桌面虚拟化中的运维工具Director SRE运维体系的构建和工作职责划分 运维的核心价值是什么 手游开发定制的全过程详解 开发人员透露:《赛博朋克2077》枪支泛滥 成熟的产品经理如何应对“这个需求不合理” CI/CD管道对开发和运维的重要性 APP开发的流程是怎样的 如何开发一个APP 零基础学web前端开发要学多久 如何系统学习 Web前端要学习哪些内容呢 前端工程师至少要满足四类客户的需求 前端学习计划思维导图 前端人如何选择自己的技术栈 前端人如何更快地成长 大数据的七大核心具体价值 核心价值究其用户到底是谁 大数据核心技术是什么 该怎么掌握Hadoop知识
您的位置:首页 >数据库 >

异或在笔试题中的超神表现

直接上题目:

1、在一组数中,其他每个数都出现了两次,仅有一个数,仅出现一次,找出这个数。2、在一组数中,其他每个数都出现了两次,仅有两个数,仅出现一次,找出这两个数。3、在一组数中,其他每个数都出现了三次,仅有一个数,仅出现一次,找出这个数。4、在一组数中,其他每个数都只出现一次,仅有一个数,出现了两次,找出这个数。

你能做出来几道?

解题思路:使用异或能极大程度的减小时间复杂度和空间复杂度。
完整源码:FindValue,源码记录的更全面,并且有测试案例。

第一道题

思路:两个相同的数进行异或为0,因此从头异或到尾,双数都被异或没了,剩下的那个就是要求的值。源码:
for (int i = 0; i < array.length; i++) {value ^= array[i];}

第二道题

思路:还是从头异或到尾,剩下的这个数,其实是这两个单独的数的异或,因为它不为0(为0说明两数想等,与题意不符)。所以我们总能找到某一位不为0的bit位,在这一位上,这两个数是不相同的,因此,根据这一位,把数组分成两组。再分别执行异或,就得到两个单独的数了。源码:
public int[] get(int[] array) {int temp = 0;for (int i = 0; i < array.length; i++) {temp ^= array[i];}int point = 1;for (int i = 0; i < 32; i++) {//从低位试探出不为0的那一位if ((temp & point) != 0) {break;}point <<= 1;}int x = 0;int y = 0;for (int i = 0; i < array.length; i++) {//根据这一位区分两堆数组,分别求独立数if ((array[i] & point) == 0) {x ^= array[i];} else {y ^= array[i];}}int[] z = new int[]{x, y};return z;}

第三道题

思路1:先考虑这种情况:我们将每个数存起来,然后数个数,谁个数是一个,我们就输出谁。现在我们不存储数字,我们存储比特位,然后将每个bit位除以3,取余,剩下的这些个bit位,留下来的都是那单一一个数的。源码:
public int method0(int[] array) {//32字节int[] bit = new int[32];for (int i = 0; i < bit.length; i++) {for (int j : array) {//判断第 i 位是否位1,31-i表示正向记录,当然也可以从低位往高位记录,最后记得反转会来即可。int u = 1 & (j >> (31 - i));bit[i] += u;}}int sum = 0;for (int i = 0; i < bit.length; i++) {//注意此处两个表达式的顺序,先移动,把bit位置空出来承接当前值sum <<= 1;sum += bit[i] % 3;}return sum;}
思路2:维持一个值,是所有出现过一次的数的异或,维持另一个值,是所有出现两次的数的异或,维持第三个值,是所有出现三次的数的异或,这些值,不停的异或数组,同时要根据取反后的其他值来刷新自己,比如说:仅记录一个数的值,需要通过和取反的记录两个数的值相与来清除自身中出现两次的数。没明白的话见参考博客,它写的比较细致。参考博客:给定一个数组,其中只有一个数出现一次,别的数都出现3次,找出这个数(go)源码:
public int method2(int[] array) {int one = 0, two = 0, three = 0;for (int x : array) {two ^= (x & one);one ^= x;three = one & two;//刷新 one 和 twoone &= ~three;two &= ~three;}return one;}

第四道题

思路:这道题大概率异或是用不了的。不考虑空间复杂度的话,使用桶排序(万一数值差距很大,会导致大量空间浪费)。考虑空间复杂度的话,牺牲时间复杂度,考虑用map(红黑树之类),最后判断谁的value是2。暂时没有想到O(n)且不浪费空间的方法,有思路请留言。

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。