剑指offer 面试题40:数组中只出现一次的数字

题目:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度为O(n),空间复杂度为O(1)

解法
分析:
如果只有一个数字出现一次,要找出这个数字,那直接依次异或,因为两个相同的数字亦或结果为0,0与任何数字异或结果还是那个数字。

现在出现两个,那么考虑分成两个子数组,但是要求成对的数字分在一起,那两个不同的数字分别在两个子数组里。

  1. 所有数字依次异或,结果为那两个不同的数字异或的结果,并且结果一定非0,记为a
  2. 从左至右找出a第一个bit位非0的index,以此为依据将原数组分为两个子数组(这样的分类标准可以达到上述的目的:1)相同的数字一定落在同一个子数组里 2)那两个不同的数字分布在不同的子数组里)
  3. 分成两个子数组后,分别异或即可
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容