欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

找到数组中只出现一次的三个数

程序员文章站 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;
}

相关标签: C++