Does anyone have a solution that does not sort and does not use a map?


  • 0
    E

    All the solutions I'm seeing here are either "sort then count" (satisfying the O(1) space constraint but not the O(n) runtime constraint) or "count by hashmap" (satisfying the O(n) runtime constraint but not the O(1) space constraint).

    Does anyone have a solution that actually satisfies the requirements?


  • 1
    M

    Solution in O(n) runtime and O(1) space

    vector<int> majorityElement(vector<int>& nums) {
        vector<int> ans;
        if (nums.size() == 0) return ans;
        int qnt = 2;
        int x = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] == x) {
                qnt += 2;
            } else {
                qnt--;
                if (!qnt) {
                    x = nums[i];
                    qnt = 1;
                }
            }
        }
        qnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == x) qnt++;
        }
        if (qnt > nums.size() / 3) {
            ans.push_back(x);
        }
        qnt = 1;
        int y = x;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == x) continue;
            if (nums[i] == y) {
                qnt++;
            } else {
                qnt--;
                if (!qnt) {
                    y = nums[i];
                    qnt = 1;
                }
            }
        }
        if (y != x) {
            qnt = 0;
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] == y) qnt++;
            }
            if (qnt > nums.size() / 3) {
                ans.push_back(y);
            }
        }
        return ans;
    }

  • 1
    W
    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            vector<int> res;
            int size = nums.size();
            int temp1=INT_MAX-1,temp2=INT_MAX-1,counter1=0,counter2=0;
            for(int i=0;i<size;i++){
                if(nums[i]==temp1) counter1++;
                else if(nums[i]==temp2) counter2++;
                else {
                    if(counter1==0) {
                        temp1=nums[i];
                        counter1++;
                    }
                    else if(counter2==0){
                        temp2=nums[i];
                        counter2++;
                    }
                    else {
                        counter1--;
                        counter2--;
                    }
                }
            }
            counter1=0;
            counter2=0;
            for(int i=0;i<size;i++){
                if(nums[i]==temp1) counter1++;
                if(nums[i]==temp2) counter2++;
            }
            if(counter1>size/3) res.push_back(temp1);
            if(counter2>size/3) res.push_back(temp2);
            return res;
            
        }
    };

Log in to reply
 

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