Java实现 LeetCode 260 只出现一次的数字 III(三)
2023-09-14 08:58:06 时间
260. 只出现一次的数字 III
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [1,2,1,3,2,5]
输出: [3,5]
注意:
结果输出的顺序并不重要,对于上面的例子, [5, 3] 也是正确答案。
你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?
PS:
1、两个相同的数异或结果为0
2、任意数异或0都为任意数
3、按位异或不同则为1,相同则为0
class Solution {
public int[] singleNumber(int[] nums) {
int key = 0;
for (int num : nums) {
key ^= num;
}
// 保留位中最右边的1,且将其余为设为0
//这两个数在1这个位置上不一样,一个是0一个是1
key = key & (-key);
int[] res = new int[2];
for (int num : nums) {
if ((num & key) == 0) {
res[0] ^= num;
} else {
res[1] ^= num;
}
}
return res;
}
}
相关文章
- Java实现 LeetCode 798 得分最高的最小轮调 (暴力分析)
- Java实现 LeetCode 795 区间子数组个数 (暴力分析)
- Java实现 LeetCode 778 水位上升的泳池中游泳(二分+DFS)
- Java实现 LeetCode 766 托普利茨矩阵(暴力)
- Java实现 LeetCode 752 打开转盘锁(暴力)
- Java实现 LeetCode 690 员工的重要性(简易递归)
- Java实现 LeetCode 633 平方数之和(暴力大法)
- Java实现 LeetCode 912 排序数组(用数组去代替排序O(N))
- Java实现 LeetCode 594 最长和谐子序列(滑动窗口)
- Java实现 LeetCode 526 优美的排列(DFS)
- Java实现 LeetCode 474 一和零
- Java实现 LeetCode 463 岛屿的周长
- Java实现 LeetCode 372 超级次方
- Java实现 LeetCode 322 零钱兑换
- Java实现 LeetCode 297 二叉树的序列化与反序列化
- Java实现 LeetCode 235 二叉搜索树的最近公共祖先
- Java实现 LeetCode 147 对链表进行插入排序
- Java实现 LeetCode 138 复制带随机指针的链表
- Java实现 LeetCode 130 被围绕的区域
- Java实现 LeetCode 123 买卖股票的最佳时机 III(三)
- Java实现 LeetCode 95 不同的二叉搜索树 II(二)
- Java实现 LeetCode 67 二进制求和
- Java实现 LeetCode 48 旋转图像
- Java实现 LeetCode 40 组合总和 II(二)
- 华为OD机试 - 区块链文件转储系统(Java & JS & Python)
- JAVA编程:java环境安装和helloworld