Majority Problem Set Summary C++


  • 0
    F

    Problem Majority 1 ------ Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

    class Solution {
    public:
    int majorityElement(vector<int> &num) {
            int majorityIndex = 0;
            for (int count = 1, i = 1; i < num.size(); i++) {
                num[majorityIndex] == num[i] ? count++ : count--;
                if (count == 0) {
                    majorityIndex = i;
                    count = 1;
                }
            }
            return num[majorityIndex];
    }
    };
    
    

    Problem Majority 2 ------ Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            int n=nums.size();
            vector<int> result;
            
            int count1=0, count2=0;
            int result1=INT_MAX, result2=INT_MAX;
            
            for(int num:nums){
                if(num==result1) count1++;
                else if(num==result2) count2++;
                else if(count1==0) { result1=num; count1=1; }
                else if(count2==0) { result2=num; count2=1; }
                else { count1--; count2--; }
            }
            
            count1=count2=0;
            for(int num:nums){
                if(num==result1) count1++;
                else if(num==result2)  count2++;
            }
            
            cout<<result1<<":"<<count1<<endl;
            cout<<result2<<":"<<count2<<endl;
            
            if(count1>n/3) result.push_back(result1);
            if(count2>n/3) result.push_back(result2);
            
            return result;
        }
    };
    

    Problem Majority 3 ------ Given an array of integers and a number k, the majority number is the number that occurs more than 1/k of the size of the array.

    class Solution {
    public:
        /**
         * @param nums: A list of integers
         * @param k: As described
         * @return: The majority number
         */
        int majorityNumber(vector<int> nums, int k) {
            const int n = nums.size();
            unordered_map<int, int> hash;
    
            for (const auto& i : nums) {
                ++hash[i];
                // Detecting k items in hash, at least one of them must have exactly
                // one in it. We will discard those k items by one for each.
                // This action keeps the same mojority numbers in the remaining numbers.
                // Because if x / n  > 1 / k is true, then (x - 1) / (n - k) > 1 / k is also true.
                if (hash.size() == k) {
                    auto it = hash.begin();
                    while (it != hash.end()) {
                        if (--(it->second) == 0) {
                            hash.erase(it++);
                        } else {
                            ++it;
                        }
                    }
                }
            }
    
            /** just re-count the possible candidate number **/
            // Resets hash for the following counting.
            for (auto& it : hash) {
                it.second = 0;
            }
    
            // Counts the occurrence of each candidate integer.
            for (const auto& i : nums) {
                auto it = hash.find(i);
                if (it != hash.end()) {
                    ++it->second;
                }
            }
    
            // Selects the integer which occurs > n / k times.
            vector<int> ret;
            for (const pair<int, int>& it : hash) {
                if (it.second > static_cast<double>(n) / k) {
                    ret.emplace_back(it.first);
                }
            }
    
            return ret[0];
        }
    };
    
    

  • 0
    F
    
    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            int n=nums.size();
            vector<int> result;
            
            int count1=0, count2=0;
            int result1=INT_MAX, result2=INT_MAX;
            
            for(int num:nums){
                if(num==result1) { count1++; continue; } 
                if(num==result2) { count2++; continue; }
                if(count1==0) { result1=num; count1=1; continue; }
                if(count2==0) { result2=num; count2=1; continue; }
                count1--; count2--;
            }
            
            count1=count2=0;
            for(int num:nums){
                if(num==result1) count1++;
                else if(num==result2)  count2++;
            }
            
            if(count1>n/3) result.push_back(result1);
            if(count2>n/3) result.push_back(result2);
            
            return result;
        }
    };
    

Log in to reply
 

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