站外题求助,可能是位运算?
  • 板块学术版
  • 楼主sunfish
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/7/28 23:55
  • 上次更新2023/11/3 07:08:16
查看原帖
站外题求助,可能是位运算?
852650
sunfish楼主2023/7/28 23:55

今天遇到了这样一道题:

将1—n的n个数随机删去两个数,再乱序排列,求被删去的数是什么, 能否使用O(1)的空间复杂度和O(n)的时间复杂度解决这个问题?

初步想到的方法是位运算:

(1)先记录这组数的总和,用1—n的总和减去这组数的总和,得到sum;

(2)1—n的异或与这组数的异或进行异或,得到丢失的两个数字的异或xor_mis;

(3)枚举判断;if((i^(sum-i))==xor_mis)

但在这里遇到了问题,比如1—6删去3,4,发现简单的判断方法会造成多解(3^4=7,3+4=7; 1^6=7,1+6=7)

实在想不到思路,特来求教,希望大佬指点一下思路,还是根本不可做?

2023/7/28 23:55
加载中...