Randomized solution


  • 0
    L

    First pick one majority element randomly. The probability of failure is calculated, the algorithm gives up when the probability is small enough.

    For the second majority element, we just pick again but exclude the one we already found.

    class Solution {
        pair<int, bool> occurAtLeast(vector<int> &a, int k, double s, bool flag = false, int exclude = 0) {
            float p = 1.;
            for (;;) {
                int i = rand() % a.size();
                if (!flag || a[i] != exclude) {
                    int cnt = 0;
                    for (const auto &x : a)
                        if (x == a[i] && ++cnt >= k)
                            return make_pair(a[i], true);
                }
                p *= (1. - s);
                if (p < 1e-6)
                    break;
            }
            return make_pair(0, false);
        }
    public:
        vector<int> majorityElement(vector<int>& nums) {
            srand(time(nullptr));
    
            const int n = nums.size();
            if (!n) return{};
    
            int k = n / 3 + 1; double p = (double)k / n;
            auto c0 = occurAtLeast(nums, k, p);
            if (!c0.second)
                return {};
    
            auto c1 = occurAtLeast(nums, k, p, true, c0.first);
            if (!c1.second)
                return { c0.first };
    
            return { c0.first, c1.first };
        }
    };

Log in to reply
 

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