我
数组中只出现一次的数字
难度:
题目:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路:
第一种方式是依次遍历数组,记录下数字出现的次数,从而找出两个只出现一次的数字。
第二种方式,根据位运算的异或的性质,我们可以知道两个相同的数字异或等于 0,一个数和 0 异或还是它本身。由于数组中的其他数字都是成对出现的,因此我们可以将数组中的所有数依次进行异或运算。如果只有一个数出现一次的话,那么最后剩下的就是落单的数字。如果是两个数只出现了一次的话,那么最后剩下的就是这两个数异或的结果。这个结果中的 1 表示的是 A 和 B 不同的位。我们取异或结果的第一个 1 所在的位数,假如是第 3 位,接着通过比较第三位来将数组分为两组,相同数字一定会被分到同一组。分组完成后再按照依次异或的思路,求得剩余数字即为两个只出现一次的数字。