二进制32位中的每一位计算“1”出现的次数只和,如果能被三整除说明只出现一次的那个数的二进制在该位也为0.如果不能被整除说明只出现一次的数的二进制数在该位是“1”,再采用左移的方式还原该位,最后使用或操作“|”将结果正确求出。
class Solution {
public int singleNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int res = 0;
int sum = 0;
for (int i = 0; i < 32; i++) {
sum = 0;
for (int num : nums) {
sum += (num >> i) & 1;
}
if (sum % 3 != 0) {
res |= 1 << i;
}
}
System.out.println(res);
return res;
}
}
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
有两个只出现一次的数字,说明至少有一位的异或值为1,根据异或值为1的位可以把数组分为两部分,分别求这俩个部分中只出现一次的数字
class Solution {
public int[] singleNumber(int[] nums) {
int[] res = new int[2];
int length = nums.length;
if(length == 2){
res[0] = nums[0];
res[1] = nums[1];
return res;
}
int bitResult = 0;
for(int i = 0; i < length; ++i){
bitResult ^= nums[i];
}
int index = findFirst1(bitResult);
for(int i = 0; i < length; ++i){
if(isBit1(nums[i], index)){
res[0] ^= nums[i];
}else{
res[1] ^= nums[i];
}
}
return res;
}
private int findFirst1(int bitResult){
int index = 0;
while(((bitResult & 1) == 0) && index < 32){
bitResult >>= 1;
index++;
}
return index;
}
private boolean isBit1(int target, int index){
return ((target >> index) & 1) == 1;
}
}
网友评论