😀前言
在数组中寻找只出现一次的两个数字是一道经典的问题,通常可以通过位运算来有效解决。本文将详细介绍这一问题的解法,深入解析其背后的思路。
🏠个人主页:尘觉主页
文章目录
- 🥰数组中只出现一次的数字
- 题目链接
- 😊问题描述
- ❤️🔥解题思路
- 😀Java 实现
- 复杂度分析
- 😄总结
🥰数组中只出现一次的数字
题目链接
牛客网
😊问题描述
给定一个整型数组,其中除了两个数字以外,其他数字均出现两次,目标是找出这两个只出现一次的数字。以数组 nums
为例:[x, x, y, y, z, k],其中 x、y 出现两次,而 z 和 k 各自只出现一次。
❤️🔥解题思路
-
利用异或运算:
- 异或运算的性质是相同的数字异或为 0,0 与任意数字异或的结果为该数字本身。根据这个性质,我们可以对数组中的所有元素进行异或操作。最终得到的结果将是这两个只出现一次的数字的异或结果。
- 举个例子,对于数组
nums
:x ^ x ^ y ^ y ^ z ^ k = 0 ^ 0 ^ z ^ k = z ^ k
。
-
分离这两个数字:
- 由于
z
和k
是不同的,z ^ k
的结果必然是一个非零的值。我们需要找到z
和k
在二进制表示上的一个不同的位。 - 我们可以通过
diff = (z ^ k) & -(z ^ k)
来找到diff
,其中diff
表示z
和k
在二进制中最右侧为 1 的位。这个位的存在可以将数组中的数字分为两类,分别与diff
进行异或运算。
- 由于
-
遍历数组分组异或:
-
再次遍历数组,根据与
diff
的异或结果将数字分为两组:
- 如果
num & diff == 0
,则将num
与第一个结果变量(如res[0]
)进行异或。 - 否则,将
num
与第二个结果变量(如res[1]
)进行异或。
- 如果
-
最终,
res[0]
和res[1]
就是我们要找的两个数字。
-
😀Java 实现
以下是用 Java 语言实现的完整代码:
public class Solution {
public int[] FindNumsAppearOnce(int[] nums) {
int[] res = new int[2];
int diff = 0;
// 第一步:计算所有数字的异或结果
for (int num : nums) {
diff ^= num;
}
// 第二步:获取 diff 最右侧的 1
diff &= -diff;
// 第三步:分组异或
for (int num : nums) {
if ((num & diff) == 0) {
res[0] ^= num; // 与 diff 的结果为 0 的数
} else {
res[1] ^= num; // 与 diff 的结果不为 0 的数
}
}
// 可选步骤:为了返回时更有序,可以选择排序
if (res[0] > res[1]) {
swap(res);
}
return res;
}
private void swap(int[] nums) {
int t = nums[0];
nums[0] = nums[1];
nums[1] = t;
}
}
复杂度分析
- 时间复杂度:O(n),需要遍历数组两次。
- 空间复杂度:O(1),只使用了常量空间来存储结果。
😄总结
通过以上的步骤,我们可以高效地找出数组中只出现一次的两个数字。利用异或运算的特性,我们能够将问题转化为位运算,简化了复杂度。这种思路不仅适用于本题,也为解决类似的问题提供了重要的思路。
😁热门专栏推荐
想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集
linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
🤔欢迎大家加入我的社区 尘觉社区
文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞