一個數組中隻有兩個數字是出現一次，其他所有數字都出現了兩次

問題描述

一個數組中隻有兩個數字是出現一次，其他所有數字都出現了兩次。

編寫一個函數找出這兩個隻出現一次的數字。

解決思路

①粗暴解決

• 每一個元素與全部元素周遊比較，未比較成功則為所要找的數字
• 這裡應注意在每次比較時，要跳過元素自己與自己比較的情況
• 時間複雜度 O(n^2)

代碼

void Find(const int* arr, size_t num)
{
	for (int i = 0; i < num; i++)
	{
		int flag = 1;

		for (int j = 0; j < num; j++)
		{
			if (j == i)
			{
				continue;
			} // 跳過元素自己與自己比較

			if (arr[j] == arr[i])
			{
				flag = 0;
				break;
			}
		}
		
		if (1 == flag)
		{
			printf("%d ", arr[i]);
		}
	}
}
           

② 通過異或解決問題

• 将所有元素挨個進行異或運算，因為隻有兩個數字不相同，其餘數字均能找到相同的一個元素，是以最終得到的結果就是兩個隻出現一次的數字的異或結果
• 分類。找到兩個數字在哪一位比特位不同，這樣根據這一位可以将數組分為兩個部分，為1的部分，為0的部分
• 再異或。在分開的兩部分中，每一部分都隻有一個隻出現一次的數字，這個數字也就是我們要找的數字之一，這樣對每一部分的每一個元素再異或運算，最終得到的結果就是所要找的數字

代碼

void Find(const int* arr, size_t num)
{
	int temp = 0;
	for (int i = 0; i < num; i++)
	{
		temp ^= arr[i];
	} // 循環結束得到的結果為所要找的兩個數字異或運算後的結果

	int flag = 0;
	while (((temp >> flag) & 1) == 0)
	{
		flag++;
	} // 得到所要找的兩個數字在哪一位比特位不同

	int ret_1 = 0;
	int ret_2 = 0;
	for (int i = 0; i < num; i++)
	{
		if ((arr[i] >> flag) & 1)
		{
			ret_1 ^= arr[i];
		} // 這是在不同的比特位為1的一組
		else
		{
			ret_2 ^= arr[i];
		} // 這是在不同的比特位為0的一組
	}
	printf("%d %d\n", ret_1, ret_2);
}