- 难度：
中等 - 本题涉及算法：
异或运算二分查找 - 思路：
异或运算二分查找 - 类似题型:
题目 面试题56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是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
方法二 二分法
- 知识提供一种思路，这个代码在leetcode 运行会超时
- 一个很棒的概念 只要符合单调，就可以二分
class Solution {
public int[] singleNumbers(int[] nums) {
int sum =0 ,min=Integer.MAX_VALUE, max = Integer.MIN_VALUE,zeroCount = 0;
for (int num:nums) {
if (num==0)
zeroCount += 1;
min = Math.min(min,num);
max = Math.max(max,num);
sum ^= num;
}
// 需要特判一下某个数是0的情况。
if (zeroCount == 1)
return new int[]{sum,0};
int lo =min,hi = max;
while (lo<=hi) {
int mid = lo<0?lo+hi >>1 :lo+(hi-lo)>>1;
int loSum =0,hiSum = 0;
for (int num:nums) {
if (num<=mid)
loSum ^= num;
else
hiSum ^= num;
}
if (loSum!=0&&hiSum!=0)
// 两个都不为0，说明 p 和 q 分别落到2个数组里了。
return new int[]{loSum,hiSum};
if (loSum==0)
// 说明 p 和 q 都比 mid 大，所以比 mid 小的数的异或和变为0了。
lo =mid;
else
// 说明 p 和 q 都不超过 mid
hi = mid;
}
// 其实如果输入是符合要求的，程序不会执行到这里，为了防止compile error加一下
return null;
}
}
解题思路 分组异或 (需要对位运算符理解很深刻)
class Solution(object):
def singleNumbers(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
ret = functools.reduce(lambda x, y: x ^ y, nums) # 运算规则：0^0=0； 0^1=1； 1^0=1； 1^1=0；
# 获得ret中最低位的1 0&0=0; 0&1=0; 1&0=0; 1&1=1;
div = 1
while div & ret == 0:
div <<= 1
a, b = 0, 0
for n in nums:
if n & div:
a ^= n
else:
b ^= n
return [a, b]
PREVIOUS面试题64. 求1+2+…+n
NEXT面试题40. 最小的k个数