数组中数字出现的次数
解题思路：
-
异或运算有以下三个性质：
- 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0 = a；
- 任何数和其自身做异或运算，结果是 0，即 a⊕a = 0；
- 异或运算满足交换律和结合律，即 a⊕b⊕a = b⊕a⊕a = b⊕(a⊕a) = b⊕0 = b；
-
数组中若「只有一个数字出现一次」，其他数字都出现两次，使用异或，最后的结果就是出现一次的数字；
-
由于该题「有两个数字出现过一次」，其他数字都出现两次，使用异或，最后的结果是出现一次的两个数字的结果，没办法分出这两个数字，所以将该数组分解成 2 个数组，每个数组都只有一个数字出现一次，其他数字出现两次；
-
分割两个数组：
- 首先获取整个数组的异或结果，也就是两个出现一次的数字的异或结果，整个异或结果假如是 1010，说明 1 的位置，两个出现一次的数字的这一位是不同的；
- 然后获取 1010 中的任意一个 1 的位置分割，这里取最后一个 1；
- 这样就能分割出两个数组，这两个出现一次的数字会被分在不同的数组里面；
复杂度：
-
时间复杂度：O(N)，线性遍历 nums 使用 O(N) 时间，遍历 x⊕y 二进制位使用 O(32) = O(1) 时间；
-
空间复杂度：O(1)，使用常数大小额外空间；
代码实现：
function singleNumbers(nums: number[]): number[] {
// 求所有数字异或和
let sum = 0;
for (let num of nums) {
sum ^= num;
}
// 找异或和第一个为 1 的位
let mask = 1;
while ((sum & mask) == 0) {
mask <<= 1;
}
// 以该位为依据分组异或
let x = 0;
let y = 0;
for (let num of nums) {
if ((num & mask) == 0) {
x ^= num;
} else {
y ^= num;
}
}
return [x, y];
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
剑指 Offer 33.二叉搜索树的后序遍历序列
上一篇
评论
