用C語言解決只出現一次的數字I II III
本章目錄
- 解題需要的C語言基礎知識
- 只出現一次的數字I
- 只出現一次的數字II
- 只出現一次的數字III
- 小編總結
解題所需要的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個題目，而是學會這種思想去解決更多的題目，同時大家有好的解題方案，也可以在評論區中留言哦，大家互相學習，一起進步，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/273258.html
標籤：其他
上一篇：我看es6之資料變化的玄妙
下一篇：詳解JS的作用域和閉包