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

Posted on by

解題所需要的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