I题目描述:
一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
解析:
位运算和Hashmap
Java:
class Solution {
public int[] singleNumbers(int[] nums) {
int a = 0, b = 0;
for(int i = 0 ; i < nums.length; i++) {
a ^= nums[i];
}
int bit = a & -a;
a = 0;
for(int i = 0; i < nums.length; i++) {
if((nums[i] & bit) == bit) {
a ^= nums[i];
} else {
b ^= nums[i];
}
}
return new int[]{a, b};
}
}
JavaScript:
var singleNumbers = function(nums) {
let map = new Map();
for(let i = 0; i < nums.length; i++) {
if(!map.has(nums[i])) {
map.set(nums[i]);
} else {
delete map.delete(nums[i]);
}
}
return [...map.keys()];
};
II题目描述:
在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
解析:
位运算和Hashmap
Java:
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
int[] count = new int[32];
for(int i = 0; i < nums.length; i++) {
for(int j = 0; j < 32; j++) {
count[31 - j] += (nums[i] >> j) & 1;
}
}
for(int i = 0; i < 32; i++) {
res <<= 1;
if(count[i] % 3 != 0) {
res |= 1;
}
}
return res;
}
}
JavaScript:
var singleNumber = function(nums) {
let res = 0;
let map = new Map();
for(let i = 0; i < nums.length; i++) {
if(!map.has(nums[i])) {
map.set(nums[i], 1);
} else {
map.set(nums[i], map.get(nums[i]) + 1);
}
}
for(let num of nums) {
if(map.get(num) === 1) {
res = num;
}
}
return res;
};