只出现一次的数字 III
# 📃 题目描述
题目链接:260. 只出现一次的数字 III (opens new window)
# 🔔 解题思路
第一步:
把所有的元素进行异或操作,最终得到一个异或值。因为是不同的两个数字,所以这个值必定不为 0;
int xor = 0;
for (int num : nums) {
xor ^= num;
}
第二步:
取异或值中随便一个二进制位为 1 的数字作为 mask,这两个只出现一次的数字在这一位上一定是不同的。
if (((sum >> i) & 1) == 1) {
k = i;
break;
}
第三步:
通过与这个 mask 进行 & 操作,如果为 0 的分为一个数组,为 1 的分为另一个数组。这样就把问题降低成了:“有一个数组每个数字都出现两次,有一个数字只出现了一次,求出该数字”。对这两个子问题分别进行全异或就可以得到两个解。也就是最终的数组了
class Solution {
public int[] singleNumber(int[] nums) {
int sum = 0;
for (int i = 0; i < nums.length; i ++) {
sum ^= nums[i];
}
int k = 0;
for (int i = 0; i < 32; i ++) {
if (((sum >> i) & 1) == 1) {
k = i;
break;
}
}
int[] res = new int[2];
// 对第 k 位分别为 0 和 1 的元素分别求异或和(两答案必然会被分到不同的组)
for (int num : nums) {
if (((num >> k) & 1) == 1) {
res[1] ^= num;
}
else {
res[0] ^= num;
}
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10