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: 3Example 2:
Input: [2,1,2,5,3,2]
Output: 2Solution
N-Repeated 因為當長度為 2N 時，會有 N+1 個位置是放置重複的數字 先將其按照順序排列，中間的數字必為其重複的 但有例外是當重複的是在最前或最後時
Random 隨機於自陣列中抽取兩個數字來比對，如是相同的馬上回傳
class Solution:
def repeatedNTimes(self, A: List[int]) -> int:
uni = []
for i in A:
if i not in uni:
uni.append(i)
else:
return iclass Solution:
def repeatedNTimes(self, A: List[int]) -> int:
while 1:
s = random.sample(A,2)
if s[0] == s[1]:
return s[0]class Solution:
def repeatedNTimes(self, A: List[int]) -> int:
count = collections.Counter(A)
for k in count:
if count[k] > 1:
return kclass 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]Last updated