如何利用C語言位運算解決隻出現一次的數字

解題所需要的C語言基礎知識

hello!從現在開始就進入本題解的正式內容瞭。首先給大傢用圖解的方式介紹3個C語言位運算的基本操作符 & | ^

這些知識對下面的解題都非常重要,一定要熟練掌握,不然等會會有一種“我在哪,我是誰我在幹什麼”的感覺。

隻出現一次的數字I

題目描述

隻出現一次的數字
給定一個非空整數數組,除瞭某個元素隻出現一次以外,其餘每個元素均出現兩次。找出那個隻出現瞭一次的元素。

說明:

你的算法應該具有線性時間復雜度。 你可以不使用額外空間來實現嗎?

示例 1:

輸入: [2,2,1] 輸出: 1
示例 2:

輸入: [4,1,2,1,2] 輸出: 4

力扣本題鏈接

解題思路

首先,根據題意,“有不可以額外使用空間這個限定”,看到這裡以後要本能的往位運算上面去靠,因為位運算可以不開辟額外空間解決很多問題,然後回看一下剛剛回顧的位運算知識,就知道我們要用到 ^這個操作符瞭,因為它可以非常簡單的消除重復項,剩下隻出現一次的數字。

說瞭這麼多,接下來讓我們來看看代碼的實現

int singleNumber(int* nums, int numsSize){
int ret=0;//0異或任何數都不會印象他的實際值
for(int i=0;i<numsSize;i++)
{
 ret^=nums[i];//所有數異或,重復的消掉,剩下隻出現一次的數字
}
return ret;//返回這個數字
}

這隻是一個開胃菜,下面正式進入主菜

隻出現一次的數字II

題目描述

隻出現一次的數字 II 給定一個非空整數數組,除瞭某個元素隻出現一次以外,其餘每個元素均出現瞭三次。找出那個隻出現瞭一次的元素。

說明:

你的算法應該具有線性時間復雜度。 你可以不使用額外空間來實現嗎?

示例 1:

輸入: [2,2,3,2] 輸出: 3
“示例 2:

輸入: [0,1,0,1,0,1,99] 輸出: 99

力扣本題鏈接

解題思路

如圖所示,考慮數字的二進制位形式,出現三次的數字,二進制位各位上的1都是三的倍數,所以求出各位上的1數目,再對3求餘,則可求出隻出現一次的數字

那麼要怎樣求取二進制位各位上1的數目吶,那就要用到&這個操作符瞭,來看代碼實現吧

int singleNumber(int* nums, int numsSize){
 
 int ret=0;
for(int i=0;i<32;++i)//循環遍歷二進制位每一位
{
long cnt=0;//不用long,力扣的編譯器不通過,不讓int類型左移31位,我也不知道
 for(int j=0;j<numsSize;++j) {//將nums數組中每一個數拿出來,二進制位向右移動i位,與1按位與,
 cnt+=(nums[j]>>i)&1;//則可求出二進制位第i位是否為1;
 }
 ret+=(cnt%3)<<i;//將cnt的值模3,求出隻出現一次的那個數第i位為1還是為0,再向左移動i位還原,最後相加求出這個數
}
return ret;
}

好瞭,這個題目就圓滿解決瞭。

隻出現一次的數字III

這個題目就很有技巧瞭 題目描述
260. 隻出現一次的數字 III 給定一個整數數組 nums,其中恰好有兩個元素隻出現一次,其餘所有元素均出現兩次。 找出隻出現一次的那兩個元素。你可以按 任意順序 返回答案。

進階:你的算法應該具有線性時間復雜度。你能否僅使用常數空間復雜度來實現?

示例 1:

輸入:nums = [1,2,1,3,2,5] 輸出:[3,5] 解釋:[5, 3] 也是有效的答案。
示例 2:

輸入:nums = [-1,0] 輸出:[-1,0]
示例 3:

輸入:nums = [0,1] 輸出:[1,0]

力扣本題鏈接

解題思路

根據第一題的思路,就知道要全部按位異或,消除重復項。但是兩個隻出現一次的數也異或在瞭一起,我們的難點就是怎麼將這兩個數分離。接下來就用圖示法來告訴大傢怎樣分離兩個數

接下來是代碼的實現

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* singleNumber(int* nums, int numsSize, int* returnSize){
int m = 0;
int ret = 0;
for (int i = 0; i < numsSize; i++)
{
	ret ^= nums[i];//將全部數異或
}
while (m < 32)
{
	if ((ret>>m)&1)//找出為1的第m位
		break;
	else
  ++m;
}
int x1 = 0, x2 = 0;//分組
int j=0;
while(j<numsSize)
{
	if ((nums[j]>>m)&1)
		x1 ^= nums[j];//異或出隻出現一次的數字
	else
		x2 ^= nums[j];
  j++;
}
int* reRer = (int*)malloc(sizeof(int) * 2);
reRer[0] = x1;
reRer[1] = x2;
*returnSize=2;//根據題意返回長度
return reRer;//返回這兩個數
}

小編總結

這是我第一次寫題解,選瞭三個相對簡單常見的題目,不難,但是也能反應出一種做題的思想。我希望大傢不是簡單的學會這3個題目,而是學會這種思想去解決更多的題目。同時大傢有好的解題方案,也可以在評論區中留言哦,大傢互相學習,一起進步。

到此這篇關於如何利用C語言位運算解決隻出現一次數字的文章就介紹到這瞭,更多相關C語言位運算解決出現數字內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀:

    None Found