O(n) Java solution using Hashtable


  • 2
    A

    I'm not sure why I'm getting times ranging from 400-550, I figured this would be faster than a simple two line sorting solution. Here it is:

    import java.util.Hashtable;
    
    public class Solution {
        public int majorityElement(int[] nums) {
            
            if (nums.length < 2) return nums[0];
            
            Hashtable<Integer, Integer> table = new Hashtable<Integer, Integer>(); 
            
            for (int i = 0; i < nums.length; i++) {
                
                if (table.containsKey(nums[i])) {
                    table.put(nums[i], table.get(nums[i])+1);
                    if (table.get(nums[i]) > (nums.length) / 2) return nums[i];
                }
                
                else table.put(nums[i], 1);
            }
            
          return 0;  
        }
    }

  • -1
    S

    This post is deleted


  • 0
    A

    The question says "You may assume that the array is non-empty and the majority element always exist in the array," so there will always be a majority element. [0,1] would not be a test case.


Log in to reply
 

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