问题一
一个数组中有一种数出现了奇数次, 其他数都出现了偶数次, 怎么找到这个种数?
在线OJ: LeetCode136. 只出现一次的数字
解题思路:
因为 a ^ a = 0, 所以出现过偶次的数异或结果都是 0, 又因为 0^a=a, 所以把数组中所有的数进行异或以后的结果, 就是出现了奇数次的那个数.
代码实现:
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for (int num : nums) {
ans ^= num;
}
return ans;
}
}
问题二
一个数组中有两种数出现了奇数次, 其他数都出现了偶数次, 怎么找到这两种数.
在线OJ: LeetCode260. 只出现一次的数字 III
根据问题一的结论, 假设数组中 a 和 b 这两个数出现了奇数次, 这个数组中的所有数字异或以后得到的结果一定 a^b, 但因为 a 和 b 是两种不同的数, 所以 a^b 的结果一定不等于 0.
所以, a^b 的结果如果转换成二进制的话, 一定至少有一个二进制位是 1.
我们假设 a^b 转换成二进制后最右侧位置的 1 在 i 位置, 由此可以得出一个结论: a 和 b 的二进制在i位置一定一个为 0, 一个为 1.
不妨假设 a 的 i 位置为 0, b 的 i 位置为 1.
此外, 容易得知, 整个数组中的数, i 位置为 0 的数除了 a 以外, 其他数一定有偶数个, i 位置为 1 的数除了 b 之外, 其他数一定有偶数个.
那么我们可以只对 i 位置为 1 的数求异或, 最后得到的值一定是 b, 然后通过 b^(a^b) = a, 可以得到 a 的值.
最后只剩下一个问题: 如何求一个数只有其最右侧的1对应的的数呢?
假设某个数x二进制为: 00010010, 那么其只有最右侧的 1 对应的数就是: 00000010.
算法是: 对于一个数 x 来说, 其只有最右侧的 1 对应的数等于 x & ((~x) + 1) 或者 x & (-x).
所以, 如果一个数是 a^b, 那么它只有最右侧的1对应的数就是 (a^b) & (~(a^b) + 1).
我们用 (a^b) & (~(a^b) + 1) 这个值去和数组中每个值进行与运算, 如果与完以后的结果是 0, 说明这个数 i 位置是 0, 否则说明这个数 i 位置是1; 我们前面已经得到一个结论, i 位置为0的数除了 a 以外, 其他数一定有偶数个; 所以, 用 (a^b) & (~(a^b) + 1) 这个值和每个 i 位置是 0 的数组元素做与运算以后, 最后的结果一定是 a; 得到 a 以后, 然后通过 a^(a^b) = b, 可以得到 b 的值.
代码实现:
class Solution {
public int[] singleNumber(int[] arr) {
int ret = 0;
for (int num : arr) {
ret ^= num;
}
// 此时ans的结果是 a ^ b 的结果
// 随便提取出 ans 随便哪一位置的 1 进行之后过程
// 因为 a ^ b 的结果的这一位置为1, 那么这两个数的这一二进制位置一定不不同, 就可以以此进行区分
// 一个数 & 上 它的相反数(取反+1)就可以可以提取出它最右侧的 1, 其余二级制位为0
int rightOne = ret & (-ret);
int ans1 = 0;
for (int num : arr) {
if ((num & rightOne) != 0) {
ans1 ^= num;
}
}
int ans2 = ret ^ ans1;
return new int[] {ans1, ans2};
}
}
当有了如下公式可以计算一个数最右侧的 1 以后, 也可以完成这样一个题
x & ((~x) + 1)
在线OJ: LeetCode191. 位1的个数
解题思路:
可以使用上面的公式提取出最右侧的 1 以后, 与目标数进行或运算, 得到一个新的目标数, 然后继续提取新目标数的最右侧的 1, 如此往复, 直到目标值为 0, 即可把所有位置的 1 都提取出来.
代码实现:
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
if (n == 0) {
return 0;
}
int count = 0;
int rightOne = 0;
while (n != 0) {
rightOne = n & (-n);
count++;
n ^= rightOne;
}
return count;
}
}
问题三
一个数组中有一种数出现 k 次, 其他数都出现了 m 次 (m > 1, k < m), 找到出现了 k 次的数.
要求: 假设数组中所有数都是 int 类型, 额外空间复杂度 O(1), 时间复杂度 O(N).
在线OJ: LeetCode137. 只出现一次的数字 II
我们可以这样考虑, 设置一个 32 位的数组,
int[] help = new int[32];
遍历原始数组中每个数 num 的每一个二进制位, 伪代码如下：
for (int num : arr) {
for (int i = 0; i < 32; i++) {
help[i] += num的二进制中i位置的值(只能是0或者1)
}
}
经过以上循环, help 数组就把数组中的所有数的二进制位上的信息累加起来了;
help[0] 表示数组中所有数二进制中0位置的值之和;
help[1] 表示数组中所有数二进制中1位置的值之和;
…
help[31] 表示数组中所有数二进制中31位置的值之和.
然后 i 从 0 位置开始拿出 help[i] 的值, 假设 help[i]=x, 用 x % m, 如果结果是 k, 说明出现 k 次的元素在这个位置上是 1, 否则, 这个出现了 k 次的数在 i 位置上是 0, 遍历完 help 数组, 出现 k 次元素的每一位信息都拿到了, 然后还原出来即可.
通用代码:
/*一个数组中有一种数出现K次，其他数都出现了M次，
已知M > 1，K < M，找到出现了K次的数, 如果不存在出现了K次的数, 返回-1
要求额外空间复杂度O(1)，时间复杂度O(N)*/
public static int onlyKTimes(int[] arr, int k, int m) {
// 用来将 arr 数组中元素相应位置二进制位为 1 的个数
int[] help = new int[32];
// 遍历arr数组
for(int num : arr) {
// 将每一个元素二进制为 1 的个数进行累加
for (int i = 0; i <= 31; i++) {
// 判断每一位二进制位值是否为 1
if (((num >> i) & 1) != 0) {
// 为 1 就累加到相应位置
help[i]++;
}
// 这个判断和 help[i] += (num >> i) & 1 等效
}
}
int ans = 0;
// 如果出现 m 次元素中的某个二进制位为 1, 那么 help 数组中相应位置的累加和一定是 m 的倍数
// 如果出现 k 次元素中某个二进制为 1, 出现 m 次元素中的这个二进制位也为 1, 那么 help 数组中相应位置的累加和一定不能被 m 整数
// 出现的不是 k 次, 但要比 m 小, 也是不能被 m 整除的, 返回-1
for (int i = 0; i < 32; i++) {
if (help[i] % m == 0) {
continue;
}
// 如果找到了不能被 m 整除的, 等于k, 那么说明结果中这个二进制位一定是为 1 的
// 不等于k, 那么除了出现 m 次的元素, 剩下的这个元素就不是出现 k 次的, 返回 -1 即可
if (help[i] % m == k) {
ans |= (1 << i);
} else {
return -1;
}
}
// 出现 k 次的元素如果是0的话, 上面的遍历就会一直 continue, 就没有判断的时机了
// 所以这里对于 0 的情况需要特殊判断一下
if (ans == 0) {
int count = 0;
for (int num : arr) {
if (num == 0) {
count++;
}
}
if (count != k) {
return -1;
}
}
// 如果题意是数组中出现 k 的数字一定存在, 可以换成下面的代码
/*for (int i = 0; i < 32; i++) {
if (help[i] % m != 0) {
ans |= (1 << i);
}
}*/
return ans;
}
解题代码:
class Solution {
public int singleNumber(int[] arr) {
int[] help = new int[32];
for(int num : arr) {
for (int i = 0; i <= 31; i++) {
if (((num >> i) & 1) != 0) {
help[i]++;
}
}
}
int ans = 0;
for (int i = 0; i < 32; i++) {
if (help[i] % 3 != 0) {
ans |= (1 << i);
}
}
if (ans == 0) {
int count = 0;
for (int num : arr) {
if (num == 0) {
count++;
}
}
}
return ans;
}
}