数组中只出现一次的数字

数组中只出现一次的数字

题目描述

解题思路：

• 如果说两个数字不是那么好处理的话，可以先想象一下，如果数组中只有一个数字只出现了一次，其他的数字都出现了两次，那么这个问题怎么解决？
• 可以想到异或运算有一个性质，任何一个数字异或他自己的结果都是0，也就是说，如果我们从头到尾依次异或数组中的每个数字，那么最终的结果就是那个数组中只出现了一次的数字，因为那些承兑出现的两个数字再异或的过程中全部都抵消了。
• 那么现在对两个数字同样进行相同的思考思路，可以尝试着把原先的数组分成两个子数组，使得每个子数组中包含一个只出现一次的数字，而其他的数字都是成对的出现两次，如果可以拆分成为两个数组的话，那么找出两个只出现一次的数字就很容易了。
• 我们还是从头到尾依次异或数组中的每个元素，那么最终得到的结果就是两个只出现了一次的数字的异或结果，又因为这两个数字肯定不一样，那么异或的结果肯定就不为0了，也就是说最后异或的结果的那个数字的二进制位中肯定有一位是1。我们可以在结果数字中找到第一个位1的位的位置，记成第n位，那么现在就可以以第n位到底是不是1来对原先的数组进行划分，将其划分为两个数组，那么这样，就把原先的数组分成两个数组了，两个数组中分别含有只出现了一次的数字，那么就很好找出来了。