LeetCode 961. N-Repeated Element

[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]