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

剑指offer:(数组)数组中只出现一次的数字

程序员文章站 2022-07-15 10:52:02
...

一、题目

1、一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这1个只出现一次的数字。要求时间复杂度为O(n),控件复杂度为O(1)
2、一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度为O(n),控件复杂度为O(1)

二、思路

1、当数组中只存在1个只出现一次的数字,遍历整个数字,并且元素异或即可得到结果。
因为其他数字都要出现2次。
a 异或 a =0
0异或 b=b
a 异或 a异或 b =b
2、现在有两个数字出现一次,那么我们还是异或所有的数,最后的到的结果就是这两个不想等的数字的异或结果,比如 2 4 3 6 3 2 5 5 最后异或就是 4 与 6 异或,那么它们两个异或的结果肯定不是0;也就是说这个结果数字的二进制当中至少有一位是1;我们在这个结果数字当中找到第一个为1的位置,记为第n位,现在我们以第n位是不是1把原来的数组分为两部分;再分别异或两个数组;分组异或。

三、代码

/*数组中只出现一次的数字*/

#include<iostream>
#include<vector>

using namespace std;

void singleNumber1(vector<int>& nums, int & num) {

	for (auto x : nums)
	{

		num ^= x;

	}
	cout << "num1:" << num << endl;

}

int find_first_bit_one(int& num)
{
	int index_bit1 = 0;
	while ((index_bit1 < 8 * sizeof(int)) && ((num & 1) == 0))
	{
		num = num >> 1;
		index_bit1++;

	}
	return index_bit1;
}


bool isbit1(int num, int& bit)
{
	num = num >> bit;
	return (num & 1);
}


void singleNumber2(vector<int>& nums, int & num1, int & num2)
{

	int lenght = nums.size();
	int xor_result = 0;
	int i;
	for (auto x : nums)
	{

		xor_result ^= x;

	}
	/*找异或值第一个出现1的位 index_first*/
	int index_first = find_first_bit_one(xor_result);

	for (auto x : nums)
	{
		if (isbit1(x, index_first))
		{
			num1 ^= x; //  x中index_first 位为1 时,与num1异或
		}
		else
		{
			num2 ^= x; // x中index_first 位不为1 时,与num2异或
		}


	}

}

int main()
{
	vector<int> a1 = { 1,1,2,2,3,4,4 };
	vector<int> a2 = { 1,1,2,2,3,4,4,5};
	int num_only=0;
	int num_only_one = 0, num_only_tow = 0;
	singleNumber1(a1, num_only);
	singleNumber2(a2, num_only_one, num_only_tow);

	cout << "1个只出现一次" << num_only << endl;
	cout << "2个只出现一次" << num_only_one << " and " << num_only_tow << endl;

	
}
相关标签: 剑指offer