My solution using random pick with O(n) time and O(1) space.


  • 0
    Q
    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) 
        {
            vector<int> res;
            if (nums.empty()) return res;
            int n(nums.size());
            for (int i = 0; i < 5; ++ i)
            {
                int id(rand() % n);
                if (count(nums.begin(), nums.end(), nums[id]) > n / 3)
                {
                    res.push_back(nums[id]);
                    break;
                }
            }
            if (res.empty()) return res;
            int nn(0), cnt(0);
            for (int a : nums)
                if (a != res.front())
                {
                    if (cnt == 0)
                    {
                        cnt = 1;
                        nn = a;
                    }
                    else
                    {
                        if (a == nn)
                            cnt ++;
                        else cnt --;
                    }
                }
            
            if (cnt && count(nums.begin(), nums.end(), nn) > n / 3)
                res.push_back(nn);
            return res;
        }
    };
    

    First we pick a number from the array randomly, and we know that the probability of get the majority element at each pick is 1/3, and if we pick three times the expectation will become 1. But in my code, I pick five times because if we just pick tree times, the probability of failure is 8/27, still a little high, but if we pick five times, it will reduce to 32/243.


    If the problem guarantees that there must be at least one majority number, we can pick repeatedly until get the right one.


    Since the time of verify is O(n), the time of pick the first one is O(5n).


    After we get the first one, it's easy to know that in the remain numbers, if there is another majority element, it must be occur more than half. So we can use Moore voting to find it.


  • 0
    B

    You are assuming there's only one majority element, but there might be two.


  • 0
    Q

    No, my solution can get two majority numbers, random pick one and vote another.


Log in to reply
 

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