My solution using Hashmap


  • 0
    S

    In addition to the usual use of the hashmap, my idea is that if we can tell for sure if a certain number can not be the majority (i.g. if a number show up for the first time after the half is passed), then we disregard to make the scan of the hash quicker.

    public class Solution {
        public int majorityElement(int[] num) {
            int n = num.length;
            
            Map<Integer, Integer> frequencies = new HashMap<Integer, Integer>();
            
            for(int i = 0; i < n; i++)  {
                Integer frequency = frequencies.get(num[i]);
                int freq = 0;
                if (frequency != null)
                    freq = frequency;
                
                if (freq + (n-i-1) < n/2 && frequency != null)   {
                    frequencies.remove(num[i]);
                } else {
                    frequencies.put(num[i], freq + 1);
                }
            }
            
            for (Map.Entry<Integer, Integer> entry: frequencies.entrySet()) {
                int freq = entry.getValue();
                if (freq > n/2) {
                    return entry.getKey();
                }
            }
            
            return 0;
        }
    }

Log in to reply
 

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