剑指 Offer 56 - I. 数组中数字出现的次数
Offer_56_1
题目描述
解题思路
java代码
/**
* 方法一：数位方法
*/
class Offer_56_1_2 {
public int[] singleNumbers(int[] nums) {
int ans = 0;
for(int num : nums){
ans^=num;
}
int pos = 1;
while((pos & ans) == 0){
pos<<=1;
}
int a=0, b=0;
for(int num :nums){
if((num & pos) == 0){
a^=num;
}else{
b^=num;
}
}
return new int[]{a, b};
}
}
复杂度分析
- 时间复杂度：O(n)，我们只需要遍历数组两次。
- 空间复杂度：O(1)，只需要常数的空间存放若干变量。