My Answer to Majority Element (Java)


  • 20
    G
    public class Solution {
    public int majorityElement(int[] num) {
        Arrays.sort(num);
        return num[num.length / 2];
    }}
    

    If to be considered majority element, a value has to occur at least N / 2 times in the array, then you can assume that if the array was to be sorted, the majority element would fill a contiguous block in the array up to (and potentially passed) the length of the array divided by 2.

    So all I did was sort the array and return the element at the array position equal to the length of the array divided by 2. Very expressive code, since it's just 2 lines, but it still took about 240ms to do since the sort algorithm needed to take its time to complete.

    Caveat: This solution only works if you can guarantee every time that there will be a majority element according to the rules set (at least N / 2 occurrences relative to the size of the array). If you can neither guarantee a majority element at all nor have the N / 2 rule in place, then this will not be suitable. If that's the case, you'll need to move onto a for-loop recording occurrences into a hash map. I tried a hash map solution which would tolerate neither of the above predicates being true, and it added about 90ms onto the running time from this solution.

    Interesting problem.


  • 1
    J

    Only because you described your approach and the reason why you did so, all Pros and Cons I will not vote Down for using sort for this problem :) very good explanation!


  • 0
    S

    I vote down because it just the solution of the solution tips


  • 0
    C

    Please find my comments here by:

    1. Using sorting and then reaching middle element, will take O(nlog(n)) + O(1) = O(nlog(n)) time. O(nlog(n)) solution is pretty costly while it can be done in O(n) time.

    2. Using HashMap to maintain count would incur O(n) extra space. Since we can solve using O(1) space we can simply rule out solution using HashMap.

    3. The questions follows Moore's Voting Algorithm. This way we can solve in O(n) time and O(1) space.


Log in to reply
 

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