文章目錄
- （1）題目描述
- （2）解題思路：分組異或
題目難度：中等
（1）題目描述
一個整型陣列
nums里除兩個數字之外，其他數字都出現了兩次，請寫程式找出這兩個只出現一次的數字，要求時間復雜度是O(n)，空間復雜度是O(1)，
示例1：
輸入：nums = [4, 1, 4, 6]
輸出：[1, 6] 或 [6, 1]
示例2：
輸入：nums = [1, 2, 3, 4, 5, 6, 1, 2, 3, 4]
輸出：[5, 6] 或 [6, 5]
LeetCode鏈接：劍指 Offer 56 - I. 陣列中數字出現的次數
（2）解題思路：分組異或
- 先來思考一下這個問題
一個整型陣列里出現一次的數只有一個，其他數字都出現了兩次，請找出這個只出現一次的數字，
要解決這個問題，利用異或的特性（兩數相同異或等于0，0和一個數異或就等于其本身），所以陣列中只有一個出現一次的數，那么只需要異或整個陣列就可以得到這個只出現一次的數，
- 回到本題，出現一次的數有兩個
假設輸入：nums = [1, 2, 3, 4, 5, 6, 1, 2, 3, 4]，我們需要從中找到 5 和 6
類比前面問題的解法，異或整個陣列，得到的是 5 和 6 的異或結果，顯然是不行，
那么我們能不能把要找的這兩個數字，分成兩組，一組放一個，這樣分別異或這兩組數，就得到了這兩個數字，
- 分組的要求
1）兩個只出現一次的數必須在不同組
2）兩個相同的數必須出現在同一組
比如分為（1 3 1 3 5）和（2 4 2 4 6），這樣就很容易找到這兩個數字了，
- 如何分組呢？（問題核心）
異或整個陣列的結果就是這兩個出現一次的數異或的結果，是一定不等于 0 的，那么說明這個異或結果的二進制序列中一定是有 1 的，找到這個 1，我們就可以利用這個來分組
nums = [1, 2, 3, 4, 5, 6, 1, 2, 3, 4]，全部異或的結果就是 5 和 6 異或的結果，即 0101 和 0110 異或的結果 0011
0011 中為1 的二進制位表示什么意思呢，分析不難知道，異或相同為 0 ，相異為 1，所以二進制位是 1，就表示 5 和 6 的二進制數在第一、二位上的數是不同的，這就是分組依據，
我們就以第一個為 1 二進制位為分組條件，將陣列中第一個二進制位為 1 的數分為一組，第二個二進制位為 0 的數分為另一組，這樣就把 5 和 6 成功分到不同的組，而剩下的那些相同的數（1 和 1、2 和 2，3 和 3、4 和 4），因為數值相同，所以它們的第一個二進制位一定是相同的，這樣就同時把兩個相同的數劃分到同一組了，
- 為了能夠更清晰的看到分組情況，我畫了一個表格：
| 陣列 | 二進制序列 | 第一個二進制位 |
|---|---|---|
| 1 | 0001 | 1 |
| 1 | 0001 | 1 |
| 2 | 0010 | 0 |
| 2 | 0010 | 0 |
| 3 | 0011 | 1 |
| 3 | 0011 | 1 |
| 4 | 0100 | 0 |
| 4 | 0100 | 0 |
| 5 | 0101 | 1 |
| 6 | 0110 | 0 |
- 分組結果為：
第一個二進制位為 1 的組（1，1，3，3，5）
第一個二進制位為 0 的組（2，2，4，4，6）
然后，分別對兩組數異或，就得到出現一次的那兩個數，
-
時間復雜度：O(N)，只遍歷了陣列兩次，
-
空間復雜度：O(1)，只需常數的空間存放若干變數，
-
參考代碼如下：
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* singleNumbers(int* nums, int numsSize, int* returnSize){
//1、異或整個陣列，得到兩個只出現一次的數字的異或結果
int ret = 0;
int i = 0;
for(i = 0; i < numsSize; i++)
{
ret ^= nums[i];
}
//2、計算ret的哪一個二進制位為1
int target = 1; //0001
while((target & ret) == 0) //按位與結果為0，說明ret的第一個二進制位為0
{
target = target << 1; //左移一位，繼續去找ret中第一個為1的二進制位
}
//回圈結束后，target中為1的二進制位在第幾位，ret的第一個為1的二進制位就在第幾位
//3、根據這一位對所有數字分組
//并分別對每一組的數字進行異或操作，得到這兩個數字
int a = 0, b = 0;
for(i = 0; i < numsSize; i++)
{
//按位與結果為0，說明nums[i]的那個二進制位為0
if((target & nums[i]) == 0)
{
a ^= nums[i];
}
else //按位與結果不為0，說明nums[i]的那個二進制位不為0
{
b ^= nums[i];
}
}
//4、動態開辟一個存放這兩個數字的陣列
int* parr = (int*)malloc(2 * sizeof(int));
parr[0] = a;
parr[1] = b;
*returnSize = 2;
return parr;
}
- 補充：計算 ret 的哪一個二進制位為1，并根據此分組，還可以這樣寫哦
//2、計算ret哪一個二進制位為1
int pos = 0; //記錄ret的第幾個二進制位為1
for(i = 0; i < 32; i++)
{
if(((ret >> i) & 1) == 1) //不斷左移，和1按位與結果為1，找到首個為1的二進制位
{
pos = i; //ret第pos位為1
break;
}
}
//3、把從高到底的第pos位為1、為0的數進行分組
int a = 0, b = 0;
for(i = 0; i < numsSize; i++)
{
//左移pos位，和1按位與結果為1，說明nums[i]第pos位為1
if(((nums[i] >> pos) & 1) == 1)
{
a ^= nums[i];
}
else
{
b ^= nums[i];
}
}
大家快去動手試一試吧！
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/295700.html
標籤：其他
下一篇：C語言之函式呼叫及堆疊幀分析