題目連結: N-Repeated Element in Size 2N Array

題目描述為: 給定一個陣列 A，大小為 2N，裡面有 N+1 個相異元素，其中有唯一元素重複出現 N 次，要我們找出該唯一元素。
題目有補充說明: 陣列 A 長度介於 [4,10000]，陣列內的元素介於 [0,10000)，且 A的大小為 2N。

例子1: A=[1,2,3,3],output=3。
例子2: A=[2,1,2,5,3,2],output=2。
例子3: A=[5,1,5,2,5,3,5,4],output=5。

思路 1: Hash 法

我們可以建立一組 map 來記錄陣列 A 裡面的元素是否出現過，當重複出現時即返回該元素。

• 複雜度評估
  重複元素分布最極端情形之一為全部集中在一起，所以至多需要遍歷 N+2 個元素才能保證能找到全部出現的元素，時間複雜度為 O(N)，此方法另外建立了一組map來記錄元素是否出現過，空間複雜度為 O(N)。

參考程式碼

func repeatedNTimes(A []int) int {
 
    m:=make(map[int]bool)
    
    for _,v:=range A{
        if !m[v]{
            m[v]=true
        }else{
            return v
        }
    }
    
    return A[0]
}

思路 2: 鴿籠原理法

此題將 N+1 個相同元素放置在大小為 2N 的陣列中，根據鴿籠原理，必存在連續3個數中可以找到重複出現的元素。我們只需依次檢查連續3個數即可。

• 複雜度評估
  重複元素分布最極端情形之一為全部集中在一起，所以至多需要遍歷 N+2 個元素才能保證能找到全部出現的元素，時間複雜度為 O(N)，此方法只使用了常數個變數，與 N 大小無關，空間複雜度為 O(1)。

參考程式碼

func repeatedNTimes(A []int) int {
    
    for i:=2;i<len(A);i++{
        
        if A[i]==A[i-1] || A[i]==A[i-2]{
            return A[i]
        }
        
        
    }

    return A[0]
}

小結:

方法 1 可應用的情境較多，若今天題目修改為尋找 A 陣列中恰出現 k 次的元素(非唯一)，此時只需要將方法 1 稍做修改，紀錄各元素出現次數即可。
方法 2 只需要 O(1) 的 空間複雜度，為此題的理想解法。而鴿籠原理尚有諸多應用。

我將解法加上簡單的測試，上傳程式碼到此。