问题描述
在一个整型数组中，除了两个数字只出现一次外，其他所有数字都出现了两次。编写一个程序来找出这两个只出现一次的数字。
示例1
输入：
[1,4,1,6]
返回值：
[4,6]
说明：
返回的结果中较小的数排在前面。
解决方案
解决这个问题的方法有很多，这里介绍两种常见的方法：使用哈希表和位运算。
方法一：哈希表
通过哈希表可以轻松找到只出现一次的两个数字。
代码思路：
1. 创建一个哈希表。
2. 遍历数组，如果当前元素不在哈希表中，则将其添加到哈希表；如果已存在，则从哈希表中移除该元素。
3. 最后哈希表中剩下的键就是只出现一次的数字。
4. 遍历哈希表的键并返回结果。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | public int[] findSingleNumbers(int[] array) {
// 创建一个哈希表
HashMap map = new HashMap<>();
for (int num : array) {
if (map.containsKey(num)) {
map.remove(num);
} else {
map.put(num, true);
}
}
// 将哈希表中的键放入结果数组
int[] result = new int[2];
int index = 0;
for (int key : map.keySet()) {
result[index++] = key;
}
return result;
}
|
这种方法简单易懂，但时间和空间复杂度均为O(n)。
方法二：位运算
位运算可以在O(1)的空间复杂度下解决问题。
总体思路：
1. 对数组中所有数进行异或运算，最终结果会得到两个不同数值的异或结果。
2. 找到异或结果中任意一个为1的位，根据这个位将数组分成两个子集，每个子集包含一个只出现一次的数字。
3. 分别对两个子集进行异或运算，得到两个只出现一次的数字。
代码实现：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | public int[] findSingleNumbers(int[] array) {
int xor = 0;
for (int num : array) {
xor ^= num;
}
// 找到异或结果中任意一个为1的位
int diffBit = xor & -xor;
int[] result = new int[2];
for (int num : array) {
if ((num & diffBit) == 0) {
result[0] ^= num;
} else {
result[1] ^= num;
}
}
// 确保结果中小的数在前
if (result[0] > result[1]) {
int temp = result[0];
result[0] = result[1];
result[1] = temp;
}
return result;
}
|
这种方法不仅时间复杂度为O(n)，而且空间复杂度为O(1)，非常适合处理大规模数据。
京公网安备 11010802041100号