找到数组中只出现一次的三个数
程序员文章站
2022-03-13 14:34:59
...
题目描述:
在一个数组中,数字都是两两成对出现的,只有三个数组出现一次,请找到这三个数。
解题思路:
1、如果是只有两个数出现一次
如果只有两个数字出现一次,首先将数组中的每一个数字进行异或,得到一个数字x,因为两个相同的数字进行异或结果是0,并且0异或任意一个数字等于原来那个数字。所以x也就表示那两个只出现一次的数字的异或。并且不等于0.因为两个数字不相等,所以必然x不等于0。根据x的比特位某一位是1,表示这两个数字该比特位不一样将数组进行分类,在依次求每个分类中的出现一次的数字即可(直接将这个数组依次异或即可)。
2、3个数字出现1次
首先将数组中的数字依次异或,等到x,x也就是这三个只出现一次的数字的异或。再将x与数组中的每一位数字进行异或,保留在原数组中。假设这三个数组是a,b,c。则现在为A=b^c,B=a^c,C=a^b。A!=B!=C!=0。现在数组中的数字依次异或为X=0。考虑X中的某一位,该为是0.0只能有0,0,0/1,1,0异或得到。那么这三个数必然有一位是不全是0的。
现在考虑如何找到这一位。对于变换后的数组,每一个数找到最低一位为1的位,并将只包含这一位的所有数进行异或便可得到这三个数最低一位为1的数异或的结果。找到这一位,必然是ABC中不全为0的位。最后根据两个1一个0将数组分割为两个数组,一个包含只有一个数字出现一次,一个包含有两个出现一次。
代码如下:
#include<iostream>
#include<vector>
using namespace std;
vector<int> singleNumbers(vector<int>& nums) {
int a=0,b=0;
int temp = 0;
for(int i:nums){
temp = temp^i;
}
int flag = 1;
while((temp&flag)==0)flag = flag<<1;
for(int i:nums){
if((i&flag)==0)a = a^i;
else b = b^i;
}
return {a,b};
}
int wei_1(int x){
if(x==0)return 0;
int res = 1;
while((x&res)==0)res = (res<<1);
return res;
}
vector<int> find_three(vector<int>& nums){
int x = 0;
// 求所有数组异或的结果
for(int num:nums)x = (x^num);
// 将x与每一个数字进行异或得到 三个单独的数组是另外两个单独数字异或的结果
for(int i=0;i<nums.size();i++){
nums[i] = (nums[i]^x);
}
// 获取这三个单独数字异或在某一位上有两个是1,一个是0。
int temp = 0;
for(int num:nums)temp = (temp^(wei_1(num)));
int flag = 1;
while((temp&flag)==0)flag = (flag<<1);
temp = flag;
// 定义两个vector一个是用来存两两相等的只有三个中的一个(temp1)
// 另一个是存三个中有两个的
vector<int> temp1;
vector<int> temp2;
for(int num:nums){
if((num&temp) == 0)temp1.push_back(num);
else temp2.push_back(num);
}
// 找到只出现一次的两个数
vector<int> res2 = singleNumbers(temp2);
// 找到只出现一次的一个数
int res = 0;
for(int num:temp1)res = (res^num);
// 最后输出的时候将这三个两两异或的数与原来的x进行异或即a^b^a^b^c = c,a^c^a^b^c = b,b^c^a^b^c = a;
return {res^x,res2[0]^x,res2[1]^x};
}
int main(){
vector<int> nums = {1,1,2,2,4,34,3,4,5};
vector<int> res = find_three(nums);
for(int num:res)cout<<num<<" ";
return 0;
}