My 2line solution


  • 4
    K

    int majorityNumber(vector<int> nums) {

        sort(nums.begin(),nums.end());
        return nums[(nums.size()/2)];
    }
    

    };


  • 0
    M

    simple & nice idea !

    if not consider time complexity then it's so simple!


  • 2
    R

    Even though it is simple , the sort operation may take you even more than O(n)


  • 0
    M

    Unless I am mistaken, this doesn't work unless the majority number is largest in the set.


  • 0
    C

    in my submission, the sort operation exceeds the time limits


  • 0

    Just write it for fun as this could be ended using only one line if you use javascript. The complexity is not so good though.

    /**
     * Memo: Sort the array first, then the majority element will be located at n/2.
     * Complex: O(nlogn)
     * Runtime: 148ms
     * Tests: 40 test cases passed
     * Rank: A
     * Updated: 2015-06-12
     */
    var majorityElement = function(num) {
        return num.sort()[num.length>>1];
    };

  • 0

    It will work, as the description says: The majority element is the element that appears more than ⌊ n/2 ⌋ times.
    So after sorting, the number will be located right in the middle.
    This is not the real definition for majority element though.


  • 0
    Y

    I think the sort() will take NlogN time on average.
    In interview, i think this solution is NOT good enough...
    If the array is sorted, then the majority number must be equal to the (N/2)th number. We can use quick select to find kth largest number, where k=N/2, N is length of the array. It took O(N) time on average.


Log in to reply
 

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