something wrong?


  • 0
    A

    Re: C++ solution using Moore's voting algorithm - O(n) runtime comlexity an no extra array or hash table
    Test the array, [1,1,1,1,1,2,3,4,5,6,7], I get answer "7", not the answer "1".
    (the array's size is 11, 11/2 = 5, so the element must appear 5 times, isn't it?)

    If I understand correctly, the question means that "the majority element appears at least n/2 times in the array".
    We assume the array is non-empty and the majority element is always exist, so the code (a simple discription) is like:

        sort(nums.begin(), nums.end()); //sort it first, then foreach
        
        int mid = nums.size() / 2;
        int count = 1; //the var, determine the number of times of the element.
        for (int i = 1; i < mid; i++) {
            if (nums[i - 1] != nums[i]) break;
            else count++;
        } //foreach [0,...,mid], the judge if the element appears n/2 times.
    
        if (count >= mid) return nums[1];
        else {
            for (int i = mid+2; i < nums.size(); i++)
                if (nums[i-1] != nums[i]) return -1;
        } //foreach [mid, ... , nums.size()-1], if it has two dif num. return -1, the majority element dont exist.
        return nums[nums.size()-1];

Log in to reply
 

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