A general solution for searching elements that appear more n/k times.


  • 8
    H

    It's based on Moore Voting Algorithm. For the question majorityElement ( finding an element that appears > n/2), return (_majorityElementOfK(nums, 3))[0];

    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
           
            if (nums.empty()) return {};
            return _majorityElementOfK(nums, 3); 
        }
        
        vector<int> _majorityElementOfK(const vector<int>& nums, int k){
            if (nums.empty()) return { };
            
            int helperSize = k - 1;
            vector<int> counters(helperSize,0);
            vector<int> elements(helperSize,0);
            
            int found = false;
          
            // find the possible elements that is greater than n/k, 
            for (int num: nums){
                found = false;
                
                for (int i = 0; i < helperSize; ++i){
                    if (!counters[i] || num == elements[i]){
                        ++counters[i];
                        elements[i] = num;
                        found = true;
                        break;
                    }
                }
                
                if (!found){
                   for (int i = 0; i < helperSize; ++i){
                        --counters[i];
                    }
                }
            }
                
            // clear the counters and re-cal to get the correct frequencies
            for (int i = 0; i < helperSize; ++i){
                 counters[i] = 0;
            }
            
            for (int i = 0; i < nums.size(); ++i){
                for (int j = 0; j < helperSize; ++j){
                    if (elements[j] == nums[i]){
                        ++counters[j];
                        break;
                    }
                }
            }
            
            // push numbers to the result if it is more than n/k
            vector<int> result;
            for (int i = 0; i < helperSize; ++i){
                if (counters[i] > nums.size()/k) result.push_back(elements[i]);
            }
            
            return result;
            
        }
    };

  • 0
    N

    Event though i got AC here this is not working for input :
    [727 727 641 517 212 532 727 100 254 106 405 100 736 727 727 787 105 713 727 333 069 727 877 222 727 505 641 533 727 727 727 508 475 727 573 727 618 727 309 486 792 727 727 426 547 727 972 575 303 727 533 669 489 727 329 727 050 209 109]

    returning : []
    expected : [727]


  • 0
    L

    That's because “num == elements[i]” should be checked separately before "!counters[i]", so that the helper slots will not have duplicates.


Log in to reply
 

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