【牛客 - 剑指offer】详解 JZ56 数组中只出现一次的两个数字 Java实现（HashMap方案 + 利用异或运算的形式）
文章目录
- 剑指offer题解汇总 Java实现
- 本题链接
- 题目
- 思路 & 代码
- 方案一 HashMap
- 方案二 异或运算
剑指offer题解汇总 Java实现
https://blog.csdn.net/guliguliguliguli/article/details/126089434
本题链接
知识分类篇 - 位运算 - JZ56 数组中只出现一次的两个数字
题目
思路 & 代码
方案一 HashMap
实现步骤：
- 使用HashMap记录数组中每个数字出现的次数
- 创建一个大小为2的int数组
- 遍历HashMap，把出现次数为1的数字放入数组中
- 比较数组中两个数字的大小，将两个数字按照非降序的顺序排列
- 最后，将排序好的数组作为返回值即可
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] FindNumsAppearOnce(int[] array) {
// write code here
HashMap<Integer, Integer> map = new HashMap<>();
for (int value : array) {
map.put(value, map.getOrDefault(value, 0) + 1);
}
int[] res = new int[2];
int i = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == 1) {
res[i++] = entry.getKey();
}
}
if (res[0] > res[1]) {
int temp = res[0];
res[0] = res[1];
res[1] = temp;
}
return res;
}
}
方案二 异或运算
- 异或运算满足交换率
- 相同的数字作异或会被抵消掉，比如：a ^ b ^ c ^ b ^ c = a
- 任何数字与0异或还是原数字
放到这个题目里面所有数字异或运算就会得到a ^ b，也即得到了两个只出现一次的数字的异或和
但是，我们想要的不是只出现一次的两个数的异或结果，而是具体得到那两个数，可以考虑将数组分成两部分，一部分为 a ^ b ^ c ^ b ^ c = a，另一部分为 b ^ x ^ y ^ y ^ x = b，怎样划分才能让a与b完全分开，且另外的数字也能成对的出现在一个组里呢？这是需要考虑的问题。
解决思路是：
- 计算数组中所有数字异或以后的结果temp
- 从右向左（其实，从右向左，从左向右都是可以的）遍历temp
- 找出二进制中第一位为1的位置，记录这个位置为1所表示的数字k。在 temp 中
- 如果某一位等于1，那么说明，a 与 b 的二进制形式在这一位上是不相同的
- 如果某一位等于0，那么说明，a 与 b 的二进制形式在这一位上是相同的
【举例】
2的二进制表示为010
4的二进制表示为100
2 ^ 4 = 010 ^ 100 = 110
从右向左看，第一位为1的是中间那位，说明，两个只出现一次的数字在第二位上的数字是不一样的，2的第二位是0，4的第二位是1
- 将数组中其他数字也按照第二位来进行分类，第二位都是1的为一组，进行异或运算，第二位都是0的为一组，进行异或运算，这样就能保证，相同的数字自然会被划分到另一边，且只出现一次的两个数字也会自然地分开
举例
import java.util.*;
public class Solution {
public int[] FindNumsAppearOnce(int[] array) {
int temp = 0;
int res1 = 0;
int res2 = 0;
for (int i : array) {
temp ^= i;
}
int k = 1;
while ((k & temp) == 0) {
k <<= 1;
}
for (int i : array) {
if ((i & k) == 0) {
res1 ^= i;
} else {
res2 ^= i;
}
}
if (res1 > res2) {
return new int[]{res2, res1};
}
return new int[]{res1, res2};
}
}