引言
對於刷題,自己是沒能力的. 最經一個朋友同事考我一道數組題 . 也許能當面試分享吧. 娛樂娛樂.
事情的開始是這樣的.
前言
題目 截圖
大概意思 是 在一個 數組中,找出其中兩個不重復出現的元素. 其它元素都是兩兩出現. 返回結果順序不要求.
好這裡 看這個系統給我們的答題界面 . 我們選擇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年. 後面也就是大白菜了......
每個時代總有忽悠的主題, 緩一緩,思索後前進總有路子,
