【原題目】:

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

 

Example 1:

Input: [1,2,3,3]
Output: 3

Example 2:

Input: [2,1,2,5,3,2]
Output: 2

Example 3:

Input: [5,1,5,2,5,3,5,4]
Output: 5

 

Note:

  1. 4 <= A.length <= 10000
  2. 0 <= A[i] < 10000
  3. A.length is even

參考 : https://leetcode.com/problems/n-repeated-element-in-size-2n-array/

 

【My Solution】:

2N個元素中,有N+1個元素是不重複,而剩下的N-1個加上在那不重複中的N+1個元素中的其中一個剛好會有N個元素重複出現

因此我們只需要找到出現一次以上的元素即為我們要的答案

1.PNG

 

【學習重點】

1. 這邊使用HashSet作為我們這次解題的容器

而不是ArrayList的原因主要在於HashSet要找容器中是否已有存在的元素來得比ArrayList還要有效率

 

boolean contains(Object o)
Returns true if this set contains the specified element.

參考 :  https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html

 

【延伸學習】

HashSet 與 HashMap的差別

HashSet :

1.實作 Set 介面

2.存放Object ( elements or values)

3.不允許有重複的元素

4.允許有一個null的元素

HashMap:

1.實作Map 介面

2.以一個key和value形式存放

3.不允許有重複的key,但可以有重複的value

4.允許一個null的key,沒有限制存放多少null的value

 

參考: https://beginnersbook.com/2014/08/hashset-vs-hashmap-java/

 

arrow
arrow
    創作者介紹
    創作者 Mark Zhang 的頭像
    Mark Zhang

    讀處

    Mark Zhang 發表在 痞客邦 留言(0) 人氣()