961. N-Repeated Element in Size 2N Array

Problem 961

https://leetcode.com/problems/n-repeated-element-in-size-2n-array/ 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

Solution

N-Repeated 因為當長度為 2N 時，會有 N+1 個位置是放置重複的數字 先將其按照順序排列，中間的數字必為其重複的 但有例外是當重複的是在最前或最後時

Random 隨機於自陣列中抽取兩個數字來比對，如是相同的馬上回傳

list

class Solution:
    def repeatedNTimes(self, A: List[int]) -> int:
        uni = []
        for i in A:
            if i not in uni:
                uni.append(i)
            else:
                return i

random

class Solution:
    def repeatedNTimes(self, A: List[int]) -> int:
        while 1:
            s = random.sample(A,2)
            if s[0] == s[1]:
                return s[0]

collection

class Solution:
    def repeatedNTimes(self, A: List[int]) -> int:
        count = collections.Counter(A)
        for k in count:
            if count[k] > 1:
                return k

N-Repeated

class Solution:
    def repeatedNTimes(self, A: List[int]) -> int:
        Length = len(A)
        A.sort()
        if( A[0] == A[1] ):
            return A[0]
        elif( A[Length-1] == A[Length-2] ):
            return A[Length -1]

        return A[(Length)//2]