首页 > 试题广场 >

数组中只出现一次的两个数字

[编程题]数组中只出现一次的两个数字

热度指数：111984 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

数据范围：数组长度 $2\le n \le 1000$ ，数组中每个数的大小 $0 < val \le 1000000$
要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

提示：输出时按非降序排列。

示例1

输入

[1,4,1,6]

输出

[4,6]

说明

返回的结果中较小的数排在前面

示例2

输入

[1,2,3,3,2,9]

输出

[1,9]

算法知识视频讲解

Python 3

蓝鲸与风

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def FindNumsAppearOnce(self , numbers: List[int]) -> List[int]:
        # write code here
        d=dict()
        for num in numbers:
            if not d.get(num):
            #target-numbers[i-1],则放入哈希表中
                d[num]=1
            else:
                d[num]+=1
        d1=sorted(d.items(), key=lambda x:x[1])
        return sorted([d1[0][0],d1[1][0]])

发表于 2022-08-20 15:23:49 回复(0)

Python 3

牛客806311391号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param array int整型一维数组
# @return int整型一维数组
#
class Solution:
def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
# write code here
# return sorted([i for i in array if array.count(i)==1])

res = {}
for i in array:
if i in res.keys():
res[i] = -1
else:
res[i] = i
return sorted([i for i in res.values() if i!=-1])

发表于 2022-08-14 19:38:00 回复(0)

Python 3

牛客213220802号

class Solution:
def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
# write code here
arr_len = len(array)
arr_res = []
for i in range(arr_len):
if array.count(array[i]) == 1:
arr_res.append(array[i])
# 注意这里题目要求输出时要按照非降序排列，所有要用sort处理下
return sorted(arr_res)

发表于 2022-08-02 11:22:09 回复(0)

Python 3

来牛客玩玩

class Solution:
    def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
        # write code here
        if len(array) < 2:
            return []
        diff = 0
        for num in array:
            diff ^= num
        diff &= -1 * diff
        num1, num2 = 0, 0
        for num in array:
            if num & diff == 0:
                num1 ^= num
            else:
                num2 ^= num
        return [num1, num2] if num1 < num2 else [num2, num1]

发表于 2022-07-26 11:32:43 回复(0)

Python 3

曰无衣bupt

借用set的去重操作其实更快：

class Solution:
    def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
        # write code here
        array1 = set(array)
        l = []
        for i in array1:
            if array.count(i) == 1:
                l.append(i)
        return sorted(l)

因为这个字符串本身冗余就很高，这样用set之后，比较几个数字就行了。

发表于 2022-06-17 20:39:16 回复(0)

Python 3

东方佑

class Solution:
    def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
        # write code here
        res_list=[]
        for i in set(array):
            if array.count(i)==1:
                res_list.append(i)
            if len(res_list)==2:
                break
        return sorted(res_list)

发表于 2022-06-08 18:26:23 回复(0)

Python 3

咸鱼翻身哈哈哈

class Solution:
def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
# write code here
list0 = []
for i in array:
if array.count(i) == 1:
list0.append(i)
list0.sort()
return list0

发表于 2022-06-04 21:41:41 回复(0)

Python 3

Vivimore

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 res

class 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)

Python 3

lun__

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
        # write code here
        from collections import Counter
        dic = Counter(array, reverse=False)
        
        res = []
        for k, v in dic.items():
            if v == 1:
                res.append(k)
        if sorted(res) != res:
            return sorted(res)  ## 用于指定顺序的情况 
        return res

发表于 2022-04-13 13:10:02 回复(0)

Python 3

牛客355096999号

用Python的字典实现：

class Solution:

def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
d={}
list1=[]
for i,j in enumerate(array):
d[j]=array.count(j)
for a,b in d.items():
if b<2:
list1.append(a)
return sorted(list1)

发表于 2022-03-11 14:39:28 回复(0)

Python 3

Joy_9

class Solution:
    def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
        # write code here
        dic={}
        for i in array:
            if i in dic.keys():
                dic[i]+=1
            else:
                dic[i]=1
        res=[k for (k,v) in dic.items() if v==1]
        res.sort()
        return res

发表于 2022-01-23 07:27:19 回复(0)

Python 3

Hudas.

class Solution:
    def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
        res = []
        new_res = set(array)
        for i in new_res:
            if array.count(i) == 1:
                res.append(i)
        return res

发表于 2021-12-28 17:46:17 回复(0)

Python 3

coders_nw

from collections import Counter

class Solution:
def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
# write code here
temp_list = sorted(Counter(array).items(), key=lambda x: (x[1], x[0]))
return([temp_list[0][0], temp_list[1][0]])

发表于 2021-12-11 01:35:16 回复(0)

Python 3

MiaoZzz

class Solution:
def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
# write code here
xor_res = 0
for item in array:
xor_res = xor_res ^ item
index = 0
for i in range(32):
if xor_res & 1 == 1:
index = i
break
xor_res = xor_res >> 1
a, b = [], []
for item in array:
if item & (2 ** index) == 0:
a.append(item)
else:
b.append(item)
res1, res2 = 0, 0
for item in a:
res1 = res1 ^ item
for item in b:
res2 = res2 ^ item
res = []
res.append(min(res1,res2))
res.append(max(res1,res2))
return res

发表于 2021-12-01 20:26:48 回复(0)

Python 3

那一勺甜

from collections import defaultdict
class Solution:
def FindNumsAppearOnce(self , array ):
# write code here
dd = defaultdict(int)
for i in array:
dd[i] += 1
res = []
for i,v in dd.items():
if v == 1:
res.append(i)
res = sorted(res)
return res

发表于 2021-10-27 12:14:47 回复(0)

Python 3

牛腩牛肉面

class Solution:
    def FindNumsAppearOnce(self , array ):
        array.sort()
        li = []
        for i in array:
            if i in li : 
                li.remove(i)
            else:
                li.append(i)
        return li

用li存放只出现一次的数据

发表于 2021-09-20 01:04:17 回复(0)

Python 3

在游泳的芭乐很胖墩墩

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型一维数组
#
# class Solution:
#     def FindNumsAppearOnce(self , array ):
#         # write code here
#         array = sorted(array,reverse=True)
# #         print(array)
#         length = len(array)
#         res = []
#         for i in range(int(length/2)+1):
#             aa = array.pop()
# #             print(aa)
#             if aa in array:
#                 array.pop()
#             else:
#                 res.append(aa)
#         return res

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型一维数组
#
# class Solution:
#     def FindNumsAppearOnce(self , array ):
#         # write code here
#         res = []
#         for i in array:
#             if i not in res:
#                 res.append(i)
#             else:
#                 res.remove(i)
#         return res

class Solution:
    def FindNumsAppearOnce(self , array ):
        # write code here
        return sorted([i for i in array if array.count(i)==1])

发表于 2021-09-11 22:17:41 回复(0)