My two line java solution


  • 37
    N
    public int majorityElement(int[] nums) {
         Arrays.sort(nums);
         return nums[nums.length/2];
    }

  • 3
    M

    I don't know why someone dislikes this solution. It's absolutely correct, and very clever actually.

    When an element appears more than n/2 times in the array, the middle one must be the "majority" number when array is sorted.

    Think about this example:

    Assume O is the "majority" and X is other numbers. The two extreme cases:

    O is at the front.

    [O O O O X X X]

    O is at the end.

    [X X X O O O O]

    They both must have the "majority" number in the middle.

    All the other cases:

    No matter how you shift X to the front or the end, O must be in the middle:

    [X O O O O X X]

    [X X O O O O X]

    There's a mathematical proof. But probably I'll just skip it.


  • 0
    C

    That was really subtle.
    Though the complexity increases due to sorting, I can't disagree that it is one of the better solutions and definitely one of the solutions that you can start with in your interviews before trying to improve for complexity.
    I will up vote you. :)


  • 1
    M

    the solution is quite great for the problem,however,when the test case is [1,2,2,3,3], the solution is 2 but the expected answer is 3 though the case or the description of the problem is not very clear


  • -21
    M

    the solution is quite great for the problem,however,when the test case is [1,2,2,3,3], the solution is 2 but the expected answer is 3 though the case or the description of the problem is not very clear


  • 2
    M

    According to the description, the 'majority' means the number appears more than half the size of the array. So your test case above doesn't have a majority number here. Thus it's not a valid case for this problem. I think the description is very clear though.


  • 0
    F

    'cause it's nlogn


Log in to reply
 

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