幫朋友 解決一道 LeetCode QJ上問題

引言

　　對於刷題,自己是沒能力的. 最經一個朋友同事考我一道數組題 . 也許能當面試分享吧. 娛樂娛樂.

事情的開始是這樣的.

前言

　　題目 截圖

大概意思 是 在一個 數組中,找出其中兩個不重覆出現的元素. 其它元素都是兩兩出現. 返回結果順序不要求. 

好這裡 看這個系統給我們的答題界面 . 我們選擇C

後面你只要做好題,就可以先 Run Code檢測,後面 Submit Solution 提交了.

下麵我會講出我的思路. 我沒有Goolge答案, 也許不是最屌解. 大家可以再優化.  

正文

1.思索演算法出路

　　首選對於演算法複雜度大於O(n),肯定不行.這裡那就採用O(n)級別的套路. 這裡有個 數學嘗試

a ^ a = 0, a ^ 0 = a, a ^ b = b ^ a. => a ^ b ^ a = a ^ a ^ b = 0 ^ b = b

其中 ^ 表示異或的意思. 記得學習電子的是偶 好像 a ⊕ b是吧,不記得了,過吧.

　　從上面算學只是我們很容易知道.

a ^ a = 0, 那麼 我們把上面 int* nums; 所有結果 異或, 最後得到 要找的兩個數的異或值.

　　好,那我們需要找出 其中一個數, 假定最後得到的數需要為 a,b

那麼上面 最後結果 就是 a ^ b => 轉成二進位碼 假如為 0x001100, 那麼 a 和 b 在第三位 和第四位 二進位是不一樣的.

那麼我們只需要找到 第一個 不一樣的二進位位數, 再把 nums 中 這些位相同的 再異或一下就得到其中一個 結果.

第一版代碼如下

 1 /**
 2  * Return an array of size *returnSize.
 3  * Note: The returned array must be malloced, assume caller calls free().
 4  */
 5 int* singleNumber(int* nums, int numsSize, int* returnSize) {
 6     int* nnums = malloc(sizeof(int)*2);
 7     int i,j,sum = 0, flag = 1;
 8     int a = 0, b;
 9     
10     // 先求所有的異或結果
11     for(i=0; i<numsSize; ++i)
12         sum ^= nums[i];
13     //找到第一個位
14     while(!(flag&sum))
15         flag <<= 1;
16     
17     for(i=0; i<numsSize; ++i)
18         if(flag & nums[i])
19             a ^= nums[i];
20     
21     nnums[0] = a;
22     nnums[1] = a ^ sum;
23     
24     *returnSize = 2;
25     return nnums;
26 }

這樣的代碼 比較普通.

測試通過要求, 下麵我會優化一下!

2.簡單優化

到這裡我們優化一下,先直接看代碼

 1 /**
 2  * Return an array of size *returnSize.
 3  * Note: The returned array must be malloced, assume caller calls free().
 4  */
 5 int* singleNumber(int* nums, int numsSize, int* returnSize) {
 6     int sl = 0, x, a = 0;
 7     int* end = nums + numsSize;
 8     int* pt = nums;
 9     //得到所有數據的異或和
10     while(pt<end)
11         sl ^= *pt++;
12         
13     // 找到第一個 位數
14     x = sl & -sl;
15     //先找到第一個數
16     while(pt > nums){
17         int t = *--pt;
18         if(x&t) 
　　　　　　　　a ^= t;   
19     }
20 
21     nums[0] = a;
22     nums[1] = a^sl;
23     *returnSize = 2;
24     return nums;
25 }

用的技巧比較多, 例如  sl & -sl 找到最低位1出現的 位置值. 例如 sl = 0x0110 => sl & -sl => 0x0010.

最後看運行結果圖

運行測試 平均時間 4ms, 第一梯隊. 可能有更好的演算法. 這裡就這樣了. 有機會 再被問,再同大家分享吧.

大家有機會有時間嘗試嘗試 LeetCode QJ.

後記

　　錯誤是難免的. 有問題留言交流. 祝 今天 陽光明媚, 現在物價太高, 日子有點難,.....

再扯一點, 30年前 一部大哥大 5000元多貴,現在印度安卓手機 包郵170, 其中150是郵費.

我覺得房價也是這樣, 租個10年. 後面也就是大白菜了......

　　每個時代總有忽悠的主題, 緩一緩,思索後前進總有路子,