My Naive Java Solution #O(3n) #HashMap #456ms


  • 0
    X

    It reminds me of a frequent pattern mining algorithm I've implemented before (Apriori). I just adapt the concept there and form a straight-forward code:

    First, counting frequency for each num, using a HashMap -- O(n)
    Second, finding largest frequency -- O(n)
    Finally, finding the "num" associated with the largest frequency found in previous step. -- O(n)

    It's not the best solution but it seems straightforward to me. Feel free to improve it...

    public int majorityElement(int[] num) {
    		HashMap<Integer, Integer> frequency = new HashMap<>();
    		for (int i = 0; i < num.length; i++) {
    			if (frequency.containsKey(num[i])) {
    				int currentFreq = frequency.get(num[i]);
    				currentFreq++;
    				frequency.put(num[i], currentFreq);
    			} else {
    				frequency.put(num[i], 1);
    			}
    		}
    
    		Integer largest = Integer.MIN_VALUE;
    		for (java.util.Map.Entry<Integer, Integer> current : frequency.entrySet()) {
    			Integer currentFreq = current.getValue();
    			if (currentFreq > largest) {
    				largest = currentFreq;
    			}
    		}
    
    		Integer resultKey = Integer.MIN_VALUE;
    		for (java.util.Map.Entry<Integer, Integer> current : frequency.entrySet()) {
    
    			if (current.getValue().equals(largest)) {
    				resultKey = current.getKey();
    			}
    		}
    
    		return resultKey;
    	}
    

    --- oh by the way this solution doesn't care about the [n/2] constraint given by the question... :(


  • 0
    G

    Nice work, here's my HashMap based solution at 324ms:

    public class Solution {
    public int majorityElement(int[] num) {
        
        int ret = 0, length = num.length;
        HashMap<Integer,Integer> elements = new HashMap<Integer,Integer>();
        
        for (int i = 0; i < length; i++) {
            int j = num[i];
            if (elements.get(j) == null) {
                elements.put(j, 1);
            }
            else {
                elements.put(j,elements.get(j) + 1);
            }
            
            if (elements.get(j) > (length / 2)) {
                ret = j;
                return j;
            }
        }
        return ret;
    }}
    

    Here's another way of going about it at 236ms:

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

  • 0
    L

    The 2nd one is, ... amazing!


Log in to reply
 

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