iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 11
0
自我挑戰組

新手也能學!一起從面試題理解程式邏輯!系列 第 11

【從面試題學邏輯-11】如何在一堆出現兩次的數中找到不重複的那位仁兄?(leetcode 136. Single Number)

首先讓我們用一題來暖身一下,個人認為其實XOR要稍微思考一下,所以選了這一題來當暖身/images/emoticon/emoticon14.gif

題目:
輸入的int陣列內,只有1個數只出現1次,其他都出現2次,寫一個方法找出那個只出現1次的數

舉例:
輸入[0,0,1,2,1,3,3]應該要拿到2

點我前往LeetCode題目頁面


那在開始前不乏提醒一下此系列的固定提醒:

這是一系列逐漸帶入解題的文章,難度會隨著進度增加,若還沒有讀過前面的文章,建議先從最前面開始來逐漸練習解題喔!


由於這已經是第二階段了,所以老樣子的暴力解就不再附上程式碼嘍!

我們先上程式碼再做解釋

class Solution {
    public int singleNumber(int[] nums) {
        int ans=0;
        for(int n : nums) {
            ans ^= n;
        }
        return ans;
    }
}

這次我們用forEach來把陣列內的東西拿出來,大家可以把for(int n : nums)這段當成是「把nums內的每個int逐一拿出來」。

那最關鍵的ans ^= n到底是有什麼功用?

大家還記得XOR的功用嗎?這段程式碼就是把ansn做XOR(Java的XOR符號是^),而XOR就是兩個不同會給1,兩個相同會給0,我們可以用這個特性來儲存「這個數字是否出現過了」。所以說原本的東西內如果沒有n,做XOR就會變成有n,如果有原本有n,做XOR就會刪掉n。

不好懂嗎?那我們看看舉例

XOR邏輯是這樣:
0 XOR 1 → 1
1 XOR 1 → 0

假設用▲代表已和陣列內部分數字XOR的一個數
▲(沒和nXOR過) XOR n → ▲(有和nXOR過)
▲(有和nXOR過) XOR n → ▲(沒和nXOR過)

這個▲原理類似我們之前說的「用來儲存字元有沒有出現過的陣列」,只是透過數字做位元運算的原理,我們可以單用1個數字來儲存是否出現過。

一定會有人問,那程式碼中的ans如果先依序和123做XOR,不會害之前的紀錄消失嗎?

不會
你可以想像ans代表的是0^1^2^3,所以之後如果再和12做XOR,就會是0^1^2^3^1^2,最後就會變成0^3,最後得到的結果就是3

解決!


看起來似乎簡單,但其實Single Number這題還有續集的第二題,讓我們多演練幾題後繼續看下去……/images/emoticon/emoticon33.gif


上一篇
【從面試題學邏輯-10】複習一下:關於位元運算(Bitwise Operation)
下一篇
【從面試題學邏輯-12】如何確認是不是2的N次方(leetcode 231. Power of Two)
系列文
新手也能學!一起從面試題理解程式邏輯!30

尚未有邦友留言

立即登入留言