EASIEST way to solve: 2 Lines C++ solution using O(n) time / O(1) space using Median idea.


  • 0
    B

    Simply the major element in an array is also it's median.

    Reasoning:
    The median divides the array into 2 halves. So an element with more than N/2 appearances will have to hit the array mid point in ranking.

    [0,1,2,3,..., median at N/2.... N-3, N-2, N-1]
         [ an array with length N/2 +1 ] will have to pass the median
    
    
    class Solution {
    public:
        int majorityElement(vector<int>& nums) {
            nth_element(nums.begin(), nums.begin() + nums.size()/2, nums.end());
            return nums[nums.size()/2];
        }
    };
    

Log in to reply
 

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