题：在一个数组中除两个数字只出现1次外，其它数字都出现了2次， 要求找出这两个数字。
解：这是另一个问题（A0）的升级版(A)，即在一个数组中只有一个数字出现了1遍，其他数字出现了两遍，要求找出这个数字。这个问题是原数组中有两个只出现了一次的数，求解起来自然费事一点。
思路：先看看A0问题，初一看，这题简单，直接弄个hash表来计算，在O(n)的时间和空间复杂度即可求出。可是这种空间复杂度是不必要的，因为有更好的办法。从另一个层面上讲，你只需要找出这个数字而已，所以使用位运算的方法更佳，原理就是通过异或运算符来操作：相同的位异或为0，反之为0，由于其他数字都出现了偶数次，所以一遍异或过后其他的数字都抵消了，最后的值就是数组中只出现一次的数字。如此看来A0问题还是比较简单的，A与A0两个貌似差不多的问题，是否具有类似方法求解呢？
其实我们可以把A1问题转化为为A0,只要我们能把数组划分为两部分，每个部分包含一个只出现一次的数字而其他数字均出现两次，这样我们就能利用A0的解法来求解A了。现在问题来了，如何转化呢？
1.将数组所有元素做异或运算，最后的结果一定等于只出现一次的两个数字的异或结果M。
2.根据M中某一位为1的位索引index，将数组的元素在index位是否为1分为两组，这样两个只出现一次的数字必然会分别落在两部分，且其他数字均出现两次，至此转化完成。
Read full article from 数组中只出现一次的数字 | 指尖的舞客
No comments:
Post a Comment