牛客网-剑指office-数组中只出现一次的数字
程序员文章站
2022-03-01 13:33:02
...
题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
解法一:
思路:首先我们会想到一个数组中只有一个数字出现一次的那道题。我们可以用异或的思想。
但这道题中有两个数字都只出现了一次,我们仍然可以利用异或的思想。我们先需要将原始数组分为两个数组,并且需要同时满足:1、两个只出现一次的数字出现在不同的数组中。2、两个相同的数字不能被分在不同的数组中。
我们可以首先遍历一遍数组,将每个数字异或。由于有两个不同的数字,所以得到的结果tmp一定不等于0.我们可以找出该结果tmp的二进制数的第一位等于1的位置index,利用这一位可以区分这两个不同的数字,并且可以保证相同的数字被分在了相同的数组中。代码如下所示:
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
int tmp=0;
for(int i=0;i<data.size();++i)
tmp=tmp^data[i];
unsigned int index =findfirst1(tmp);
*num1 = 0;
*num2 = 0;
for(int i=0;i<data.size();++i)
{
if(isbit1(data[i],index))
num1[0]=num1[0]^data[i];
else
num2[0]=num2[0]^data[i];
}
}
unsigned int findfirst1(int num)
{
int index = 0;
while(((num&1)==0)&&(index<32))
{
num=num>>1;
++index;
}
return index;
}
int isbit1(int num,unsigned int index)
{
num=num>>index;
return num&1==1;
}
};
解法二:
思路:建立一个set容器,然后遍历数组,如果数字已经存在于set容器中,则删除该数字,如果没有存在,则将该数字放入set容器中,最后剩下的数就是只出现一次的两个数字。
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
set<int> tmp;
for(int i=0;i<data.size();++i)
{
if(tmp.count(data[i])==1)
tmp.erase(data[i]);
else
tmp.insert(data[i]);
}
vector<int> ans;
for(set<int>::iterator iter = tmp.begin();iter!=tmp.end();++iter)
{
ans.push_back(*iter);
}
*num1 = ans[0];
*num2 = ans[1];
}
};
python的解法:
思路:利用c++的第二种解法的思路。
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
ans = []
for num in array:
if num in ans:
ans.remove(num)
else:
ans.append(num)
return ans
上一篇: 牛客刷题数组之数组中只出现一次的数字
下一篇: C语言实现十进制数转二进制数输出
推荐阅读
-
【剑指offer】面试题56(1):数组中只出现一次的两个数字
-
剑指offer:数组中只出现一次的两个数字(java版)
-
剑指offer 面试题56 python版+解析:数组中只出现一次的两个数字,数组中唯一只出现一次的数字
-
剑指offer第二版-56.数组中只出现一次的两个数字
-
【算法分享】剑指offer56-数组中只出现一次的两个数字
-
剑指 Offer 56 - I. 数组中只出现一次的两个数字
-
剑指56:数组中只出现一次的数字——异或——位运算
-
《剑指Offer》Java刷题 NO.40 数组中只出现一次的数字(数组、HashMap、位运算、异或)
-
【剑指】56(1).数组中只出现一次的两个数字
-
剑指Offer_编程题40:数组中只出现一次的数字(异或)