General solution for > (n/k) occurences


#1

This solution is the general version of Moore’s Voting Algorithm for majority element.
This works in O(k) extra space and O(n) time.

int Solution::repeatedNumber(const vector<int> &A) {
    const int k = 3;
    int n = A.size();
    vector<int> cnt(k, 0), candidate(k, -1);
    for (int i = 0; i < n; i++) {
        bool updated = false;
        for (int j = 0; j < k; j++) {
            if (candidate[j] == A[i]) {
                cnt[j]++, updated = true;
                break;
            }
        }
        if (updated) continue;
        for (int j = 0; j < k; j++) {
            if (cnt[j] == 0) {
                cnt[j]++, updated = true;
                candidate[j] = A[i];
                break;
            }
        }
        if (updated) continue;
        for (int j = 0; j < k; j++)
            cnt[j]--;
    }
    cnt.assign(k, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < k; j++) {
            if (candidate[j] == A[i]) {
                cnt[j]++;
                break;
            }
        }
    }
    for (int j = 0; j < k; j++)
        if (cnt[j] > n / k) return candidate[j];
    return -1;
}

#2

Do you have any source from where I can understand this? It’s a bit hard to understand.