???樊梓慕：個人主頁

???個人專欄：《C語言》《數(shù)據(jù)結(jié)構(gòu)》《藍橋杯試題》

??每一個不曾起舞的日子，都是對生命的辜負。

目錄

前言：

一只單身狗：

兩只單身狗：

前言：

本篇主要講解LeetCode上的經(jīng)典題型：只出現(xiàn)一次的數(shù)字，我匯總了該類問題的兩種情況（一只單身狗、兩只單身狗）并進行分析講解和代碼實現(xiàn)，學習完本篇文章你會掌握一種全新的思路：異或法，希望大家多多支持博主創(chuàng)作，博主會持續(xù)帶來更多優(yōu)質(zhì)內(nèi)容??

=========================================================================

GITEE相關代碼：??fanfei_c的倉庫??

=========================================================================

一只單身狗：

LeetCode原題鏈接：??只出現(xiàn)一次的數(shù)字??

題目：給你一個?非空?整數(shù)數(shù)組?nums?，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。

傳統(tǒng)方法我們可以想到利用計數(shù)器，但這種算法效率不理想。

今天我們就來學習異或法。

首先我們來復習一下位操作符：

&：兩個數(shù)字對應二進制位有0則為0，兩個同時為1才是1。

|：兩個數(shù)字對應二進制位有1則為1，兩個同時為0才是0。

^：兩個數(shù)字對應二進制位相同為0，相異為1。

• ?想要具體了解位操作符的同學可以移步這里??位操作符的應用，他會幫助你對本篇內(nèi)容的理解更加透徹。

我們知道兩個相同的數(shù)字異或得到的結(jié)果為0，而0^某個數(shù)字就是它本身，且異或操作符滿足交換律。

那么既然給定的該數(shù)組nums滿足只有其中一個元素出現(xiàn)一次，其他數(shù)字都出現(xiàn)兩次的情況，我們就可以利用^的特性來梳理邏輯：將nums數(shù)組的內(nèi)容異或到一起，此時相同的數(shù)字就都異或為0了，剩余一個單獨的數(shù)字與0異或得到它本身。

代碼實現(xiàn)：

int find_single_dog1(int arr[], int sz)
{
	int i = 0;
	int ret = 0;
	for (i = 0; i < sz; i++)
	{
		ret ^= arr[i];
	}
	return ret;
}

int main()
{
	int arr[] = { 1,2,3,4,7,1,2,3,4 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int dog = find_single_dog1(arr, sz);
	printf("%d\n", dog);
	return 0;
}

兩只單身狗：

LeetCode原題鏈接：??只出現(xiàn)一次的數(shù)字(2)??

題目：給你一個整數(shù)數(shù)組?nums，其中恰好有兩個元素只出現(xiàn)一次，其余所有元素均出現(xiàn)兩次。 找出只出現(xiàn)一次的那兩個元素。你可以按?任意順序?返回答案。

假設仍然按照異或法的邏輯能不能實現(xiàn)呢？

其實我們只需要將兩只單身狗的問題轉(zhuǎn)化為一只單身狗就好了，需要做的就是將兩只單身狗分開處理，這樣就到了我們熟悉的領域了。?

那么我們?nèi)绾尾拍軐芍粏紊砉贩珠_呢？

我們假設數(shù)組為：1，2，3，4，5，1，2，3，4，6。

觀察如果將該數(shù)組異或到一起得到：5^6。

?根據(jù)異或的特性我們知道兩個不相同的二進制數(shù)字異或的結(jié)果為1，那么我們可不可以根據(jù)這一特性來區(qū)分兩個單身狗呢，我們可以利用數(shù)組異或的結(jié)果取一個位為1的位，在該位上，與5相同的分為一組，與6相同的分為一組。

比如：

?分完組后是不是很熟悉，沒錯就是一只單身狗的處理方法了。

代碼實現(xiàn)：

void find_single_dog2(int arr[], int sz, int* pd1, int* pd2)
{
	//1. 所有數(shù)字異或在一起
	int ret = 0;//5 ^ 6
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		ret ^= arr[i];
	}

	//2. 計算ret的第幾位是1
	int pos = 0;
	for (i = 0; i < 32; i++)
	{
		if (((ret >> i) & 1) == 1)
		{
			pos = i;
			break;
		}
	}

	//計算數(shù)組中元素的第pos為1的異或
	for (i = 0; i < sz; i++)
	{
		if (((arr[i] >> pos) & 1) == 1)
		{
			*pd1 ^= arr[i];
		}
	}
	//計算數(shù)組中元素的第pos為0的異或
	*pd2 = ret ^ *pd1;
}

int main()
{
	int arr[] = { 1,2,3,4,5,1,2,3,4,8 };
	int dog1 = 0;
	int dog2 = 0;
	int sz = sizeof(arr) / sizeof(arr[0]);
	find_single_dog2(arr, sz, &dog1, &dog2);//dog1、dog2為返回型參數(shù)
	printf("%d %d", dog1, dog2);
	return 0;
}

?單身狗問題是筆試非常高頻的題型，掌握了這種方法相信會使你的解題思路更加清晰，如果本篇文章對你有幫助，希望多多支持博主，博主會持續(xù)創(chuàng)作優(yōu)質(zhì)內(nèi)容??文章來源地址http://www.zghlxwxcb.cn/news/detail-603313.html

到了這里，關于【LeetCode】260.只出現(xiàn)一次的數(shù)字 III（找出單身狗）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！