My Java Solution With O(n) Time ( use a hashmap)


  • -1
    E

    public static List<Integer> majorityElement(int[] nums) {

        List<Integer> list = new ArrayList<Integer>();
       
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();// use hashmap to store the count
        
        for( int i = 0 ; i < nums.length; i ++){
        	if(map.get(nums[i]) == null ){//if this number is not set
        		map.put(nums[i] , 1);
        	}else{//if the number is set, increase the count
        		map.put(nums[i], map.get(nums[i]) + 1);
        	}
        	
        }
        
        for(Integer in : map.keySet()){//there is at most 2 numbers that appear more than 1/3 times.
        	if( map.get(in) > nums.length/3)
        		list.add(in);
        }
        
        return list ;
    }

  • 0
    J

    how do u guarantee O(1) space


Log in to reply
 

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