[C++/Java/Python] 4 lines O(1) O(1)
Solution 1
Use array or set and return seen number at once.
O(N) time, O(N) space
Java, use array
public int repeatedNTimes(int[] A) {
int[] count = new int[10000];
for (int a : A)
if (count[a]++ == 1)
return a;
return -1;
}
C++, use set
int repeatedNTimes2(vector<int>& A) {
unordered_set<int> seen;
for (int a: A) {
if (seen.count(a))
return a;
seen.insert(a);
}
}
Solution 2
Random pick two numbers.
Return if same.
C++:
int repeatedNTimes(vector<int>& A) {
int i = 0, j = 0, n = A.size();
while (i == j || A[i] != A[j])
i = rand() % n, j = rand() % n;
return A[i];
}
Java:
public int repeatedNTimes(int[] A) {
int[] count = new int[10000];
for (int a : A)
if (count[a]++ == 1)
return a;
return -1;
}
Python:
def repeatedNTimes(self, A):
while 1:
s = random.sample(A, 2)
if s[0] == s[1]:
return s[0]
