一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
数据范围：数组长度 
，数组中每个数的大小 
要求：空间复杂度)
，时间复杂度 )
要求：空间复杂度
提示：输出时按非降序排列。
[编程题]数组中只出现一次的两个数字
用异或^可解此题。
但是首先要知道一个知识点，a^b^a = a^a^b = b^a^a =b，这个知识点也就是本题的简单版本：如果数组中除了某一个数字，其他数字都出现了两次，找出该数字。思路就是遍历数组，对每一个数字都求异或，最后得到的值就是要找的数字。
有了该知识点的储备，再来看看本题。本题是要找两个数字a和b，那我们把该数组分成两个数组，其中a和一部分出现两次的数字在一块儿，b和另一部分出现两次的数字在一块儿，那这两个数组不是就变成了上面讲的那个简单版本中的数组吗？然后再分别对这两个数组求异或，就可以找到这两个数字了。
举例：[a,2,2,3,3,b]。把该数组分成[a,2,2]和[3,3,b]，再对这两个数组求异或，便能得到a和b。
问题：怎么把a和b区分开来？
可以利用二进制来区分。先对整个数组求异或得到c，根据上面的知识，可以知道c其实就是a^b=c。那么对于c，假如c二进制的第一位是1，其实就代表a二进制的第一位是1（或0），b二进制的第一位是0（或1），总而言之如果第一位的c等于1，那么a和b在第一位肯定不相等。
所以我们就可以想到利用二进制的第一位（有可能是第二位，第三位 。。。因为上面是假设的c第一位是1）为1来区分两个数组，第一位为1的是数组一，第一位为0的是数组二。这样就相当于把a和b给区分开来了。
a和b区分开以后，剩下的就简单了，判断数组中其他数字的二进制的第一位是否为1，是的话就分到数组一，为0就分到数组二。最后对数组一和数组二分别进行异或，得到的就是a和b。
有个地方没有讲清楚，利用二进制的第一位为1来区分两个数组，如果第一位不是1，那就判断第二位，第三位，一直到找到为1的地方。假设一直找到第n位才为1，那就判断数组中的其他数字的二进制的第n位是否为1，做&运算即可判断。
位运算感觉还是挺抽象的，我也是用具体的例子来照着别人的代码推一遍才搞明白，为什么那个地方做&运算就可以得到它，为什么那个地方做^运算又可以得到它。要是还没看懂的小伙伴也可以自己写一个具体的数组，然后照着代码先在草稿纸上推一遍，多搞几次就明白了。
最后附上js代码
function FindNumsAppearOnce( array ) {
// write code here
var res = 0; //对整个数组求异或的结果
for(var i = 0; i < array.length; i++){
res ^= array[i];
}
var compare = 1;
while((compare & res) == 0){ //判断异或结果的二进制第一位是否为1，为1则直接跳过该循环
compare <<= 1; //为0则继续往后找，一直到找到为1的二进制位，该行代码也相当于compare *=2
}
var a = 0;
var b = 0;
for(var i = 0; i < array.length; i++){ //遍历数组，开始判断数字们的compare位是否为1
if((compare & array[i]) == 0){ //如果该数字二进制的第某位为0，则分到数组一
a ^= array[i]; //对数组一进行异或，得到a
}else{ //如果该数字二进制的第某位为1，则分到数组二
b ^= array[i]; //对数组二进行异或，得到b
}
}
return a < b ? [a,b] : [b,a];
}
编辑于 2021-03-30 14:05:22
回复(11)
如果只有一个数字仅出现一次，其余都出现两次，则所有数字异或的结果就是那个仅出现一次的数字。
此题中，有两个数字只出现一次，所有数字异或的结果一定非0，其二进制表示中一定有某一位为1，可根据这一位是否为1，将数组分为两部分，则两部分的所有数字分别做异或，得到的两个结果就是要求的两个结果。
class Solution: def FindNumsAppearOnce(self , array ): # write code here if not array: return [] res = 0 for i in array: res = res ^ i index = 0 while res & 1 == 0: res = res >> 1 index += 1 a, b = 0, 0 for i in array: if self.helper(i, index): a = a ^ i else: b = b ^ i return [a, b] if a < b else [b, a] def helper(self, num, index): num = num >> index return num & 1 != 0
发表于 2021-02-26 10:08:05
回复(1)
20210925#之前没注意到空间复杂度，写了这么个答案，多谢牛友提醒
思路很简单，遍历一遍，第一次遇到的数字加入到map中，若第二次遇到，从map中去除，最终map只剩下两个出现过一次的数字，两个数字转换成vector类型，排序后输出。
class Solution {
public:
vector<int> FindNumsAppearOnce(vector<int>& array) {
// write code here
unordered_map<int,int> map;
vector<int> res;
for(auto it:array){
if(map.find(it)!=map.end()) map.erase(it);//若已经出现过一次，删掉
else map[it]++;}//若第一次出现，保留
for(auto it:map)//此时map里只剩两个数字，取出来，存到vector类型的res里边
res.push_back(it.first);
sort(res.begin(),res.end());//从小到大排序
return res;}};
编辑于 2021-09-25 21:07:03
回复(5)
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param array int整型一维数组
# @return int整型一维数组
#
class Solution:
def FindNumsAppearOnce(self , array ):
# write code here
return sorted([i for i in array if array.count(i)==1])
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param array int整型一维数组
# @return int整型一维数组
#
class Solution:
def FindNumsAppearOnce(self , array ):
# write code here
return sorted([i for i in array if array.count(i)==1])
发表于 2021-08-09 16:39:22
回复(3)
import java.util.*;
// 利用HashMap的key值去重，但是代码要求了输入的顺序性，比如 传入 {3,6}必须返回{3,6}不能是{6，3}，所以第二个for循环是为了保证顺序，不然直接可以返回key的值
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public static int[] FindNumsAppearOnce (int[] array) {
// write code here
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>(array.length);
for (int n : array) {
if (map.get(n) != null) {
map.remove(n);
} else {
map.put(n, n);
}
}
int index = 0;
for (int n : array) {
if (map.get(n) != null) {
result[index] = map.get(n);
index ++;
}
}
return result;
}
}
// 利用HashMap的key值去重，但是代码要求了输入的顺序性，比如 传入 {3,6}必须返回{3,6}不能是{6，3}，所以第二个for循环是为了保证顺序，不然直接可以返回key的值
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public static int[] FindNumsAppearOnce (int[] array) {
// write code here
int[] result = new int[2];
Map<Integer, Integer> map = new HashMap<>(array.length);
for (int n : array) {
if (map.get(n) != null) {
map.remove(n);
} else {
map.put(n, n);
}
}
int index = 0;
for (int n : array) {
if (map.get(n) != null) {
result[index] = map.get(n);
index ++;
}
}
return result;
}
}
发表于 2021-03-16 13:56:25
回复(2)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param nums int整型一维数组
* @return int整型一维数组
*/
public int[] FindNumsAppearOnce (int[] nums) {
// write code here
HashSet<Integer> set = new HashSet<>();
for (int num : nums) {
if (set.contains(num)) {
set.remove(num);
} else {
set.add(num);
}
}
return set.stream().sorted().mapToInt(Integer::intValue).toArray();
}
}
发表于 2024-05-07 11:41:56
回复(0)
class Solution:
def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
res = []
for num in array:
if num in res:
res.remove(num)
else:
res.append(num)
res.sort()
return res
发表于 2022-10-04 16:07:48
回复(1)
class Solution:
# 异或运算：相同数字为0，相异数字为1
# 空间复杂度：O(1) 时间复杂度：O(n)
def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
res = [0, 0]
temp = 0
for i in range(len(array)):
temp ^= array[i] # 0 ^ 数 = 数
k = 1
# 找到两个数不相同的第一位
while k & temp == 0:
k <<= 1 # 左移，右边补零
for i in range(len(array)):
# 遍历数组，对每个数分类
if k & array[i] == 0:
res[0] ^= array[i]
else:
res[1] ^= array[i]
res.sort()
return resclass Solution:
# 哈希表
# 空间复杂度：O(n) 时间复杂度：O(n)
def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
mp = {}
res = []
for i in array:
if i in mp:
mp[i] += 1
else:
mp[i] = 1
for i in mp:
if mp[i] == 1:
res.append(i)
res.sort()
return res
发表于 2022-05-10 09:23:46
回复(0)
# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param array int整型一维数组 # @return int整型一维数组 # class Solution: def FindNumsAppearOnce(self , array ): import collections array_count = collections.Counter(array) return [key for key,value in array_count.items() if value==1] # write code here
发表于 2021-03-02 08:44:58
回复(1)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型vector
* @return int整型vector
*/
vector<int> FindNumsAppearOnce(vector<int>& array) {
// write code here
int temp=0;
for(int i=0;i<array.size();i++){
temp^=array[i];
}
int ll=1;
while(1){
if(temp&ll)break;
ll<<=1;
}
int a=0,b=0;
for(int i=0;i<array.size();i++){
if(ll&array[i])a^=array[i];
else b^=array[i];
}
if(a<=b){
return {a,b};
}else{
return {b,a};
}
}
};
发表于 2021-02-26 15:11:12
回复(0)
int* FindNumsAppearOnce(int* nums, int numsLen, int* returnSize ) {
*returnSize=2;
int* arr = (int*)malloc(sizeof(int)*2);
int tmp[1000000]={0};
for(int i = 0;i<numsLen;i++)
{
tmp[nums[i]]++;
}
int count = 0;
for(int i = 0;i<1000000;i++)
{
if(tmp[i]==1)
{
arr[count++]=i;
}
}
return arr;
}
发表于 2024-12-20 00:16:41
回复(1)
class Solution:
def FindNumsAppearOnce(self , nums: List[int]) -> List[int]:
lst=[]
for i in set(nums):
n=nums.count(i)
if n==1:
lst.append(i)
return lst
def FindNumsAppearOnce(self , nums: List[int]) -> List[int]:
lst=[]
for i in set(nums):
n=nums.count(i)
if n==1:
lst.append(i)
return lst
发表于 2024-08-08 10:55:43
回复(0)
hashMap
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] FindNumsAppearOnce (int[] array) {
// write code here
int[] res = new int[2];
Arrays.sort(array);
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < array.length; i++) {
if (map.containsKey(array[i])) {
map.put(array[i], map.get(array[i]) + 1);
} else {
map.put(array[i], 1);
}
}
int k = 0;
for (int i = 0; i < array.length; i++) {
if (map.get(array[i]) == 1) {
res[k] = array[i];
k++;
}
}
return res;
}
}
发表于 2022-06-17 15:22:36
回复(0)
import java.util.*;
public class Solution {
public int[] FindNumsAppearOnce (int[] array) {
// 使用HashMap统计数值出现的次数
// key -- 数值，value -- 该数值出现的次数
Map<Integer, Integer> red = new HashMap<>();
// ans用来保存结果值
int[] ans = new int[2];
// index用来控制ans的索引，指向当前数值存储的位置
int index = 0;
// 扫描一次数组，进行统计
for(int num : array)
red.put(num, red.getOrDefault(num, 0) + 1);
// 扫描一次HashMap，寻找之出现一次的数值并记录
// 当index等于2，说明已经找到了这两个数值，不必继续扫表
for(Map.Entry<Integer, Integer> entry : red.entrySet()){
if(entry.getValue() == 1)
ans[index ++] = entry.getKey();
if(index == 2)
break;
}
// 结果需要非降序排列，因此这里做了个排序
Arrays.sort(ans);
return ans;
}
}
发表于 2021-11-14 10:04:30
回复(0)
思路：
用哈希表需要额外的空间。时间复杂度为O(n)，空间复杂度为O(n)。
用位运算则不需要。时间复杂度为O(n)，空间复杂度为O(1)。
异或(^)，两个数二进制对应位数相同为0，不同为1。
两个相等的数异或为0,0和一个数异或等于这个数。
这道题用的是a^b^b等于a。
因为有a和b不同，剩下都是两两重复的数。先把数组元素全部异或一遍，得到的数为a^b。
通过a^b来得到从右到左第一个1保留，剩下都为0的变量m。
m的这个1可以把a和b分开，剩下成对元素的分组无所谓，最后异或都会为0。
通过遍历和判断放到res[0]和res[1]。
public int[] FindNumsAppearOnce (int[] array) {
int[] res = new int[2];
if(array == null || array.length == 0) return res;
//0和谁异或(^)都是该数本身
int x = 0;
for(int i = 0;i < array.length;i++){
x ^= array[i];
}
int m = 1;
//想要的是m左移后的那个数
while((x & 1) != 1){
x >>= 1;
m <<= 1;
}
res[0] = res[1] = 0;
//左移后得到的m可以把数组分为2组
for(int i = 0;i < array.length;i++){
//但是m和array[i]与运算结果是m本身或0
if((array[i] & m) == m){
res[0] ^= array[i];
}else{
res[1] ^= array[i];
}
}
//把大的放到res[1]
if(res[0] > res[1]){
int temp = res[0];
res[0] = res[1];
res[1] = temp;
}
return res;
} 可以用Set，用HashSet实现。
（HashSet底层由HashMap实现，所以HashMap和HashSet的默认大小都是16）
涉及到HashSet的遍历：
可以用for(int item : set)的形式来遍历到元素。
这种增强for循环能遍历java中的大多数集合。
编辑于 2021-03-26 17:56:36
回复(4)
public class Solution {
public int[] FindNumsAppearOnce (int[] array) {
// 用以提取异或结果
Function<IntPredicate, Integer> getXor = (intPredicate) -> Arrays.stream(array)
.filter(intPredicate).reduce((a, b) -> a ^ b).getAsInt();
// 提取全量数据的异或结果
int xorResult = getXor.apply(a -> true);
// 取全量异或结果的末位
int lastBit = xorResult ^ (xorResult & (xorResult - 1));
int[] result = new int[2];
// 按数据与全量异或结果的末位是否相等，进行二次异或
result[0] = getXor.apply(a -> (a & lastBit) == lastBit);
result[1] = getXor.apply(a -> (a & lastBit) == 0);
Arrays.sort(result);
return result;
}
}
发表于 2021-03-09 11:34:48
回复(0)
class Solution:
def FindNumsAppearOnce(self , nums ):
# write code here
dict1 = {}
for val in nums:
dict1[val] = dict1.get(val, 0) + 1
keys = [key for key,value in dict1.items() if dict1[key] == 1]
if keys[0] < keys[1]:
return [keys[0], keys[1]]
else:
return [keys[1], keys[0]]
发表于 2025-08-13 14:34:53
回复(0)
思路简单，就是定义一个hash表，存每个数及出现的次数，当这个数再次出现时，把这个数从表里删除，最后排序输出
class Solution: def FindNumsAppearOnce(self , nums: List[int]) -> List[int]: # write code here result = dict() for num in nums: if num in result: result.pop(num) else: result[num] = 1 return sorted(result.keys())
编辑于 2024-04-17 20:41:56
回复(0)
int* FindNumsAppearOnce(int* nums, int numsLen, int* returnSize ) {
int HashTable[1000000] = {0}, i, j, *res;
res = (int*)malloc(2*sizeof(int));
for (i = 0; i < numsLen; i++)
HashTable[nums[i]]++;
for (i = 0, j = 0; i < sizeof(HashTable); i++) {
if (HashTable[i] == 1)
res[j++] = i;
if(j>=2)
break;
}
*returnSize = 2;
return res;
}
编辑于 2024-03-20 21:42:40
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-02-22 11:49:23
-
2023-02-20 11:08:57
-
2022-10-30 15:19:04 -
2022-10-27 16:26:43
-
2022-09-26 19:37:31
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
