Java: O(n) solution using HashMap


  • 1
    H
    public int majorityElement(int[] nums) {
    	int n = nums.length;
    	if(n < 3) return nums[0];
    	int m = (n % 2 == 0) ? n / 2 : n /2 + 1;
    	
    	HashMap<Integer,Integer> map = new HashMap<>();
        for(int key : nums)
        {
        	if(!map.containsKey(key)) map.put(key, 1);
        	else
        	{
        		int count = map.get(key);
        		if(count + 1 >= m) return key;
        		map.put(key, count + 1);
        	}
        }
        return 0;
    }

  • 0
    J

    Here is my HashMap sol.

    public class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> list = new HashMap<Integer, Integer>();
        for(int i=0; i<nums.length; i++){
            if(!list.containsKey(nums[i])){
                list.put(nums[i],1);
            }
            else{
                list.put(nums[i],list.get(nums[i])+1);
            }
        }
        int re = 0;
        for(Integer i:list.keySet()){
            if(list.get(i)>nums.length/2){
                re = i;
            }
        }
        return re;
      }
    }

  • 0
    G

    I did mine this way too. Faster than 0.57% of answers lol! Definitely the noobie way.


  • 0
    G

    You can also use a for each for the first loop btw.


Log in to reply
 

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