面试题56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
题解：
1.整型数组 nums
2.数字有出现两次和两个出现一次的
3.返回这两个出现一次的
4.时间复杂度是O(n)，空间复杂度是O(1)
示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
限制：
2 <= nums <= 10000
解题思路：位异或分组
题目对时间开销和空间开销要求都很高，放松条件可以考虑哈希表等其它方法；这里考虑二进制异或运算。
-
出现两次的数字通过异或两两抵消等于0(二进制异或)
-
因为成对的两两抵消变0，0^x=x,整个数组异或后,即剩余出现一次的这两个数的异或值
-
如果异或值某位为1，则最后这两个数一个是1一个是0，依此分组
-
这样出现两次的相同数一定会被分到一组，这样这两个结果数又被分到了两个组里，比如说a被分到了一组，b被分到了二组；这样每组里除了a和b其它都是出现两次的数
-
再对每一组都异或一次，这样一组异或后的值就是a(其它两两相同的数异或等于0,而0^a=a)
C/C++题解：
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int x = 0;
for (int val : nums) x ^= val;//整个数组异或一次，剩只出现一次的两个数的异或值
int flag = x & (-x); //选取最低位分组
int res = 0;
for (int val : nums) {
if ((flag & val) != 0) {//区分成两组
res ^= val;}//这里只对一组进行全部异或
}// 因为一开始x是两个数的异或值，分组后再异或一组找到的是其中的一个数
//所以第二个数也就是用这两个数的异或结果再异或其中一个
return {res, x ^ res};}};
Debug结果：
Java题解：
class Solution {
public int[] singleNumbers(int[] nums) {
int x = 0;
for (int val : nums) x ^= val;//整个数组异或一次，剩只出现一次的两个数的异或值
int flag = x & (-x); //选取最低位分组
int res = 0;
for (int val : nums) {
if ((flag & val) != 0) {//区分成两组
res ^= val;}//这里只对一组进行全部异或
}// 因为一开始x是两个数的异或值，分组后再异或一组找到的是其中的一个数
//所以第二个数也就是用这两个数的异或结果再异或其中一个
return new int[] {res, x ^ res};}}
Debug结果：
Python题解：
class Solution(object):
def singleNumbers(self, nums):
""":type nums: List[int]:rtype: List[int] """
x = 0
for val in nums: x ^= val #整个数组异或一次，剩只出现一次的两个数的异或值
flag = x & (-x) #选取最低位分组
res = 0
for val in nums:
if ((flag & val) != 0): #区分成两组
res ^= val#这里只对一组进行全部异或
#因为一开始x是两个数的异或值，分组后再异或一组找到的是其中的一个数
#所以第二个数也就是用这两个数的异或结果再异或其中一个
return [res, x ^ res]
Debug结果：
更多题解算法的聚集地可前往公众号获取