描述
题目描述
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
示例
输入：[1,4,1,6] 返回值：[4,6] 说明：返回的结果中较小的数排在前面
引言
首先看到这道题，抠字眼: 两个数字只出现一次，其他的数字都出现了两次，两个 “两” 是解题关键。
知识点：位运算，分治，数组，集合
难度：⭐⭐⭐
题解
解题思路
1 异或
异或的特性是：两个数字相同，则异或结果为0，两个数字不同，则其二进制位的异或结果为 1，如 4 ^ 6 = 100 ^ 110 = 010。
异或运算一般要将数字转化为二进制位，再进行运算，相同则为0，不同则为 1。
因此，看到数组里其他数字都出现两次，那么就应该联想到异或的特性，使得所有元素异或后，出现两次的数字异或都都为0。
因此异或结果后就只剩下两个只出现一次的数字，接下来问题就好解决多了。
2 分治思想，问题降维
通过与运算求出两个目标值的异或结果的最右边的 1 作为标记
通过 mark 与数组每个元素的异或结果不同，将数组分为两组，分别存放到结果集里
反正相同的两个数组都会分到同一组
两组分别异或后结果都会只下最后的两个单独数字
方法一：分治+异或
图解
算法流程：
- 先进行异或，结果是两个单独的数异或的结果
- 通过与运算求出两个目标值的异或结果的最右边的 1作为标记
- 根据 mark 将原数组分为两组，单独出现的两个数字分在不同的组
- 返回的结果中较小的数排在前面
Java 版本代码如下：
import java.util.*;
public class Solution {
public int[] FindNumsAppearOnce (int[] array) {
int[] ans = new int[2];
int mark = array[0];
// 先进行异或，结果是两个单独的数异或的结果
// 假如array为[1,4,1,6]，则 mark =1 ^ 1 ^ 4 ^ 6 = 0^4^6 = 4 ^ 6=010
for (int i = 1; i < array.length; i++) {
mark ^= array[i];
}
// 通过与运算求出两个目标值的异或结果的最右边的 1作为标记
// 如 mark = 010-010&001=010,只保留最右边的1作为mark
mark -= mark & (mark - 1);
for (int i = 0; i < array.length; ++i) {
//根据mark将原数组分为两组，单独出现的两个数字分在不同的组
if((mark & array[i]) == 0) {
ans[0] ^= array[i];
} else {
ans[1] ^= array[i];
}
}
// 题目要求，返回的结果中较小的数排在前面
if(ans[0] > ans[1]) {
int temp = ans[0];
ans[0] = ans[1];
ans[1] = temp;
}
return ans;
}
} Python 版本代码如下：
class Solution:
def FindNumsAppearOnce(self , array ):
# write code here
ab = 0
# 进行异或，结果是两个单独的数异或的结果
for item in array:
ab = ab ^ item
sep = 1
while sep & ab == 0:
sep = sep << 1
a, b = 0, 0
for item in array:
# //根据mark将原数组分为两组，单独出现的两个数字分在不同的组
if item & sep:
a = a^item
else:
b = b^item
# 题目要求，返回的结果中较小的数排在前面
return [a, b] if a < b else [b, a] 复杂度分析：
时间复杂度O(N)：位运算时需要遍历数组所有元素，N 为数组长度
空间复杂度O(1)：只用到了常量级别的整形数据
总结：掌握位运算的特性对于解决一些难题无往不利
方法二：集合
算法流程：
- Java 的 Set 或 Python 中的元组 + 字典，通过出现次数保存只出现一次的结果集
- 如果 Set 中有这个值，说明重复了，则删除 set 中该数字，保证 set 中数字都是唯一
- 若第一次出现，加入集合中
- 只出现一次，则加入结果集
Java 版本代码如下：
import java.util.*;
public class Solution {
public int[] FindNumsAppearOnce (int[] array) {
// 升序排序
TreeSet<Integer> set = new TreeSet<>((o1, o2) -> o1 - o2);
int[] res = new int[2];
for (int i = 0; i < array.length; ++i) {
// 如果 Set 中有这个值，说明重复了
if (set.contains(array[i])) {
// 有重复值，则删除 set 中该数字，保证 set 中数字都是唯一
set.remove(array[i]);
} else {
// 若第一次出现，加入集合中
set.add(array[i]);
}
}
int index = 0;
for (Integer i : set) {
res[index++] = i;
}
return res;
}
} Python 版本代码如下：
class Solution:
def FindNumsAppearOnce(self , array ):
# 字段的value存放数字出现次数
d = {}
li = []
# 将给定数组当作键值
for i in range(len(array)):
# 根据制定键返回相应的值，设置默认值为0
d[array[i]] = d.get(array[i], 0) + 1
# 返回字典的键值对组成的元组格式
for key, value in d.items():
# 只出现一次
if value == 1:
li.append(key)
return li复杂度分析：
时间复杂度 O(NlogN)：for 循环内的 TreeSet 操作的时间复杂度为 logN
空间复杂度 O(N)：用到集合、字典等数据类型，N 为数组长度
京公网安备 11010502036488号