题目:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度为O(n),空间复杂度为O(1)
解法
分析:
如果只有一个数字出现一次,要找出这个数字,那直接依次异或,因为两个相同的数字亦或结果为0,0与任何数字异或结果还是那个数字。
现在出现两个,那么考虑分成两个子数组,但是要求成对的数字分在一起,那两个不同的数字分别在两个子数组里。
- 所有数字依次异或,结果为那两个不同的数字异或的结果,并且结果一定非0,记为a
- 从左至右找出a第一个bit位非0的index,以此为依据将原数组分为两个子数组(这样的分类标准可以达到上述的目的:1)相同的数字一定落在同一个子数组里 2)那两个不同的数字分布在不同的子数组里)
- 分成两个子数组后,分别异或即可