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

  • 0

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

    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 {
        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.