題目連結:
題目意譯:
在一個大小 2N 的陣列 A 中,有著 N + 1 種相異元素,且其中恰好一個元素重複出現了 N 次。
回傳重複出現 N 次的那個元素。
注:
4 ≦ A.length ≦ 10000
0 ≦ A[i] < 10000
A.length 為偶數。
範例測資:
範例 1:
輸入: [1,2,3,3]
輸出: 3
範例 2:
輸入: [2,1,2,5,3,2]
輸出: 2
範例 3:
輸入: [5,1,5,2,5,3,5,4]
輸出: 5
解題思維:
因為這題會出現的值最大為 10000,所以直接開一個陣列統計 0 ~ 10000 之間所有數字的數量。
掃過陣列 A,一旦有數字出現超過 1 次(出現第二次),則代表該數字即是所求。
而如果數字很大,可以改為統計每一位元為 1 的次數(如
這題的精神),掃過所有數字後再掃一次統計的位元,每個位元只要至少 n 次為 1,則代表該位元包含在所求數字中。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。