前往
大廳
主題

LeetCode - 961. N-Repeated Element in Size 2N Array 解題心得

Not In My Back Yard | 2021-02-24 00:00:05 | 巴幣 0 | 人氣 127

題目連結:


題目意譯:
在一個大小 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,則代表該位元包含在所求數字中。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作