菲洛嘉青春动能素135HA FILLMED® NCTF 135HA LED指示灯的常见故障分析 智微智能 Elkhartlake K075终端,零售产业新选择 天空蓝拓客管理系统详细介绍版 muso公链项目 天使计划 是什么?[秘] 独家揭秘最前沿的家装“黑科技”——掌赋 天博体育欧洲杯特辑,东道主法兰西的失意2016 亚马逊的送货侦察员 学习听起来像挡泥板 Google Comics Factory使ML变得容易 笑着说-男性或女性 Amazon Rekognition中更好的人脸检测 关于Spaun的真相-大脑模拟 两个聊天机器人彼此聊天-有趣又怪异 GANPaint:将AI用于艺术 WCF和WF给予社区 从耳朵到脸 所有神经网络的深层缺陷 蠕虫在尾巴上平衡杆子 Kickstarter上的OpenCV AI套件 TensorFlow-Google的开源AI和计算引擎 众包取代新闻工作者 Google的DeepMind学会玩街机游戏 哑机器人V智能机器人 .NET与.NET 5融为一体 Google的深度学习-语音识别 LInQer将.NET LINQ移植到Javascript 机器人TED演讲-新的图灵测试? GAN的发明者加入苹果 您的智能手机会监视您键入的内容 人工智能帮助改善国际象棋 Zalando Flair NLP库已更新 TensorFlow 1.5包含移动版本 AlphaGo输了一场比赛-比分3-1 虚拟机器学习峰会 Microsoft开源AI调试工具 SharePoint走向移动 F#4.0发出文化变革的信号 克里斯蒂拍卖AI艺术品 人工智能如何区分 Facebook在蒙特利尔的新AI实验室 Mozilla想要您的声音 微软使用极深的神经网络赢得ImageNet 建立AI合作伙伴关系 .NET Core 3-Microsoft几乎回到了起点 神经网络-更好的销售商? Google使用AI查找您的住所 虹膜-适用于Android的Siri证明苹果没有优势 TensorFlow 2提供更快的模型训练 深度学习研究人员将为Google工作
您的位置:首页 >数据库 >

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

直接上题目:

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)且不浪费空间的方法,有思路请留言。

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