首页 > 试题广场 >

数组中只出现一次的数字

[编程题]数组中只出现一次的数字
  • 热度指数：450661 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
算法知识视频讲解
查看答案及解析
添加回答
推荐
张佃鹏头像 张佃鹏 
class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
  if(data.size()<2)
   return ;
  int size=data.size();
  int temp=data[0];
  for(int i=1;i<size;i++)
   temp=temp^data[i];
  if(temp==0)
   return ;
  int index=0;
  while((temp&1)==0){
   temp=temp>>1;
   ++index;
  }
  *num1=*num2=0;
  for(int i=0;i<size;i++)
  {
   if(IsBit(data[i],index))
    *num1^=data[i];
   else
    *num2^=data[i];
  }
    }
 bool IsBit(int num,int index)
 {
  num=num>>index;
  return (num&1);
 }
};
可以用位运算实现，如果将所有所有数字相异或，则最后的结果肯定是那两个只出现一次的数字异或
 的结果，所以根据异或的结果1所在的最低位，把数字分成两半，每一半里都还有只出现一次的数据和成对出现的数据
 这样继续对每一半相异或则可以分别求出两个只出现一次的数字
编辑于 2015-08-18 23:24:57 回复(77)
Python
牛客344478146号头像 牛客344478146号

哈希

元素依次进栈，若重复出现则出栈，最后输出字典余下的键即为不重复的数字

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        hashtable={}
        for i,num in enumerate(array) :
            if num in hashtable :
                del hashtable[array[i]]
            else:
                hashtable[num]=i
        return hashtable.keys()
编辑于 2020-11-07 16:55:50 回复(0)
Python
ztfmars123头像 ztfmars123
python有作弊神器啊，凡事设计统计个数、频率的数列，都可以用Counter统计个数，最后都会返回
{"key1":count1, "key2":count2},直接使用统计的出现频率信息进行下一步判断就可以了。非常轻松。

# -*- coding:utf-8 -*-
import collections
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        if len(array)<2:
            return None
        num=[]
        tmp = collections.Counter(array)
        for k, v in tmp.items():
            if int(v) % 2 == 1:
                num.append(int(k))
        return num[0], num[1]
发表于 2020-09-12 16:54:33 回复(0)
Python
kite97头像 kite97 
    def FindNumsAppearOnce(self, array):
        # write code here
        res = []
        for num in array:
            if array.count(num) == 1:
                res.append(num)
                if(len(res) == 2):
                    break
        return res
笨蛋如我想不到异或的做法
发表于 2020-09-08 09:54:28 回复(0)
Python
牛客702212974号头像 牛客702212974号
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        lis = []
        for i in array:
            count = array.count(i)
            if count == 1:
                lis.append(i)
        return lis[0], lis[1]
发表于 2020-08-07 16:15:20 回复(0)
Python
DDooo头像 DDooo 
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        import collections
        c = collections.Counter(array)
        list = []
        for k in c:
            if c[k] == 1:
                list.append(k)
        return list
和前面的“数组中出现次数超过一半的数字”的题目很像，于是我仍然利用collection.Counter()函数，将数值和次数做成字典，然后搜索次数为1对应的数并输出。下面是我之前出错的地方： 
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        import collections
        c = collections.Counter(array)
        
        for k in c:
            if c[k] == 1:
                return k
我使用案例代入，发现：

他只输出第一次计数次数为1的值，其他的次数为1的值如“3”并不输出，很奇怪。。。。
于是我查了一下return的用法，发现：return语句用于退出函数，向调用方返回一个表达式。执行到return语句时，会退出函数，return之后的语句不再执行。所以return在这里只执行一次，并退出了函数。
编辑于 2020-07-26 17:34:29 回复(0)
Python
q2Lin头像 q2Lin 
思路：先排序，则相同的数字一定相连。遇到下一个数相同，i+2，否则i即为只出现一次的数，i+1。

class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        array.sort()#先排序
        res = []
        i = 0
        while i < len(array):
            if i == len(array)-1 and array[i-1] != array[i]:#末尾位置的情况
                res.append(array[i])
                i += 1
            elif array[i] != array[i + 1]:
                res.append(array[i])
                i += 1
            else:#遍历到两个相同的数i+2
                i += 2
        return res

发表于 2020-07-24 20:53:01 回复(0)
Python
牛客小飞侠~头像 牛客小飞侠~
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        if not array:
            return []
        temp = set()
        for i in array:
            if i not in temp:
                temp.add(i)
            else:
                temp.remove(i)
        return list(temp)
发表于 2020-07-11 06:57:07 回复(0)
Python
Cloud_9头像 Cloud_9 
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        A = []
        for i in array:
            a = array.count(i)
            if a == 1:
                A.append(i)
        return A
python。不是最优解  但是我感觉这个算比较容易想到的

编辑于 2020-06-13 11:06:41 回复(0)
Python
Kuriyamaaa头像 Kuriyamaaa 
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        flag=[]
        re=[]
        for i in range(len(array)):
            if array[i] not in flag:
                
                if array[i]in array[i+1:len(array)+1]:
                    
                        flag.append(array[i])
                else:
                    re.append(array[i])
        return re
                        
        # write code here

发表于 2020-05-27 15:56:17 回复(0)
Python
牛客124928456号头像 牛客124928456号 
    def FindNumsAppearOnce(self, array):
        # write code here
        return(list(filter(lambda i:array.count(i)==1,array)))

编辑于 2020-05-21 21:20:29 回复(0)
Python
小白白小头像 小白白小 


使用时间为22，内存5644 class Solution：
    def FindNumsAppearOnce(self, array):
        # write code here
        list = []
        for demo in array:
            if demo not in list:
                list.append(demo)
            else:
                list.remove(demo)
        return list


编辑于 2020-04-06 15:44:00 回复(1)
Python
华电美男头像 华电美男 
利用字典：
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        (2128)# write code here
        if not array:
            return []
        dit=dict()
        li=[]
        for num in array:
            if num in dit:
                dit[num]+=1
            else:
                dit[num]=1
        for k,v in dit.items():
            if v==1:
                li.append(k)
        return li


发表于 2020-03-26 13:21:04 回复(0)
Python
但行好事-莫问前程头像 但行好事-莫问前程
建立hash表，统计数组中所有数据出现的次数
  1. 建立hash表：用字典实现hash表
  2. 统计数组中所有数字出现的次数：若当前数字在表中，则次数+1，否则初始化其value == 1
  3. 遍历hash表，输出value == 1的key（数字） 
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        (2128)# write code here
        dic = dict()
        for i in range(len(array)):
            if array[i] in dic:
                dic[array[i]] += 1
            else:
                dic[array[i]] = 1
        res = []
        for key, value in dic.items():
            if value == 1:
                res.append(key)
        return res
            


发表于 2020-03-11 10:12:40 回复(0)
Python
(•̀∀•́)6头像 (•̀∀•́)6
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    
    def FindNumsAppearOnce(self, array):
        list=[]
        for i in range(len(array)):
            j = i
            b = array[i]
            if b not in array[:j] and b not in array[j + 1:]:
                list.append(b)
        return list
发表于 2020-03-08 15:50:53 回复(0)
Python
牛客447097232号头像 牛客447097232号 
# -*- coding:utf-8 -*-
"""
异或操作
p xor q = q xor p
(p xor q) xor r =  p xor (q xor r)
p xor 0 = p

位运算

"""
class Solution:
    (1250)# 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        if not  array:
            return []
        res_xor_all = 0
        # 相同的数字全部抵消，不同的数字使得结果至少某一位为1
        for a in array:
            res_xor_all ^= a
        (1251)# 从右往左，第一个1的位置
        index = self.find_first_one(res_xor_all)
        res1 = 0
        res2 = 0
        for a in array:
            # 元素第index位是1的一组，不是1的一组
            if self.is_group(a,index):
                res1 ^= a
            else:
                res2 ^= a
        return [res1, res2]

    def find_first_one(self, a):
        index = 0
        while a & 1 == 0:
            a = a >> 1
            index += 1
        return index

    def is_group(self, a, index):
        return a >> index & 1


s = Solution()
ans = s.FindNumsAppearOnce([1,2,5,2])
print(ans)

发表于 2020-03-03 13:16:58 回复(0)
Python
FocusVay头像 FocusVay
请输入正确的答案及 
class Solution:

    def FindNumsAppearOnce(self, array):
        
        lst1 = []
        lst2 = []
        
        def wBin(num):
            str2 = list(bin(num))
            str1 = str2[::-1]
            for i in range(len(str1)):
                if str1[i] == '1':
                    return i
                
        def OnlyNum(lstS):
            lst0 = lstS
            num1 = 0
            for i in range(len(list(lst0))):
                num1 = num1^lst0[i]
            return num1
        
        Bkey = wBin(OnlyNum((array)))

        for i in range(len(array)):
            if wBin(array[i]) == Bkey:
                lst1.append(array[i])
            else:
                lst2.append(array[i])

        return OnlyNum(lst1),OnlyNum(lst2)

解题思路
发表于 2020-02-19 15:08:16 回复(0)
Python
没有offer的祈求者头像 没有offer的祈求者 
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        L = []
        for n in array:
            if n in L:
                L.remove(n)
            else:
                L.append(n)
        return L
//核心思想，有就删除，没有就加入。剩到最后的就是落单的两个。

编辑于 2020-01-10 15:18:03 回复(0)
Python
黄沙遮天头像 黄沙遮天 
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        dict1={}
        for i in array:
            l1=array.count(i)
            if i not in dict1:
                dict1[i]=l1
        list1=[]
        for key,value in dict1.items():
            if value==1:
                list1.append(key)
        return list1
采用的空间换时间的方法，计算每个数字出现的次数，然后将出现次数为1的键拿出来
发表于 2020-01-04 22:37:32 回复(0)
Python
天山剑客头像 天山剑客 
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        return list(filter(lambda x: array.count(x) == 1, array))

发表于 2019-12-02 15:42:12 回复(0)
Python
Kirto先森头像 Kirto先森 
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        #已知: 整型数组中只出现一次的数字，可以用异或来解决
        #那么当有两个只出现一次的数字时，数组异或的最终结果将是这两个数字的异或结果
        #设数组的异或结果的二进制最后一位1是第n位(为什么选1,因为异或运算只有位上数值不同才会得到1)
        #根据第n位的二进制值来将数组划分为两部分，而这两个数字分布于两个部分
        
        #解题步骤
        #1.获取数组异或结果
        #2.找到异或结果二进制最后一个1的位置
        #3.将数组按该位置划分成两部分
        #4.两部分分别异或得到两个只出现一次的数字
        
        #1.获取数组异或结果
        xor = array[0]
        for val in array[1:]:
            xor ^= val
        print(xor)
        
        #2.获取二进制1的位置
        loc = 0
        for val in bin(xor)[::-1]:
            if val=="1":
                break
            loc += 1
        print(loc)
        
        #3.数组划分和异或同时进行
        flag1 = True
        flag2 = True
        for val in array:
            if bin(val)[-(loc+1)]=='1':
                if flag1:
                    xor1 = val
                    flag1 = False
                else:
                    xor1 ^= val
            else:
                if flag2:
                    xor2 = val
                    flag2 = False
                else:
                    xor2 ^= val
        return [xor1, xor2]
                

发表于 2019-11-19 16:42:28 回复(0)
提交观点

问题信息

位运算 哈希
难度：
91条回答 159256浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号