Boyer-Moore Majority Volting Algorithm Generalized to k (appear more than n/k times)


  • 0
    A
    vector<int> majorityElement(vector<int>&nums, int k) {
        vector<int> result;
        if (k < 2) return result;
        // there are at most k-1 candidates
        vector<int> candidates(k-1, 0);
        vector<int> count(k-1, 0);
        
        // initialize candidates array with different values
        // otherwise, the all zeros nums vector will fail
        for (int i = 0; i < k-1; ++i)
            candidates[i] = i;
        
        // first loop, if one candidate appears more than n/k times, 
        // the maximal number of times it can be offset by other candidates is n/k
        for (int num : nums) {
            bool found = false;
            for (int j = 0; j < k-1; ++j) {
                if (num == candidates[j]) {
                    ++count[j];
                    found = true;
                    break;
                }
            }
            
            if (!found) {
                for (int j = 0; j < k-1; ++j) {
                    if (count[j] == 0) {
                        candidates[j] = num;
                        ++count[j];
                        found = true;
                        break;
                    } 
                }
            }
            if (!found) {
                for (int j = 0; j < k-1; ++j) {
                    --count[j];
                }
            }
        }
        
        // second loop: find candidates that appear more than n/k times
        count.assign(k-1, 0);
        for (int num : nums) {
            for (int j = 0; j < k-1; ++j) {
                if (candidates[j] == num)
                    ++count[j];
            }
        }
        
        for (int j = 0; j < k-1; ++j) {
            if (count[j] > nums.size()/k)
                result.push_back(candidates[j]);
        }
        return result;
    }

  • 0
    M

    This is not the constant space solution as asked in problem


  • 0
    X

    because it's Generalized


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.