二进制运算
a=0^a=a^0
0=a^a
由上面两个推导出:a=a^b^b
a=a^b
b=a^b
a=a^b
a=n&(n-1)
diff=(n&(n-1))^n
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
public int singleNumber(int[] nums) {
// 10 ^ 10 == 00
// 两个相同的数异或变成0
int result = 0;
for (int n : nums) {
result = result ^ n;
}
return result;
}
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现了三次。找出那个只出现了一次的元素。
public int singleNumber(int[] nums) {
int result = 0;
// 统计每位1的个数
for (int i = 0; i < 64; i++) {
int sum = 0;
for (int n : nums) {
// 统计1的个数
sum += ((n >> i) & 1);
}
// 还原
result |= ((sum % 3) << i);
}
return result;
}
给定一个整数数组nums
,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
public int[] singleNumber(int[] nums) {
// 关键点怎么把a^b分成两部分,方案:可以通过diff最后一个1区分
int diff = 0;
for (int n : nums) {
diff ^= n;
}
int[] result = new int[]{diff, diff};
// 去掉末尾的1后异或diff就得到最后一个1的位置
diff = (diff & (diff - 1)) ^ diff;
for (int n : nums) {
if ((diff & n) == 0) {
result[0] ^= n;
} else {
result[1] ^= n;
}
}
return result;
}