My Easy Understand Java solution with explain


  • 0
    Y

    Using Moore’s Voting Algorithm according to GeeksforGeeks.
    Maintain 2 nums and their counts at most.
    Three cases to consider:

    1. If the new number is in the count map, increase its count;
    2. If count map size is less than 2, add new number;
    3. if new number is not in count map and map has size of two, decrease the count for all
      numbers in map.
              public List<Integer> majorityElement(int[] nums) {
                    Map<Integer, Integer> majority = new HashMap<Integer, Integer>();
                    List<Integer> result = new ArrayList<Integer>();
                   
                    for (int i: nums) {
            			if (majority.containsKey(i)) {
            				majority.put(i, 1 + majority.get(i));
            			} else if (majority.size() < 2) {
            				majority.put(i, 1);
            			} else {
            				decreaseCountAndDelete(majority);
            			}
            		}
                    for (Integer key:majority.keySet()) {
                        int count = 0;
                        for (int i:nums) {
                            if (i == key) count++;
                        }
                        if (count > nums.length / 3) {
                            result.add(key);
                        };
                    }
                    return result;
                }
                private void decreaseCountAndDelete(Map<Integer, Integer> map) {
                    for (Map.Entry<Integer, Integer> entry:map.entrySet()) {
            			map.put(entry.getKey(), entry.getValue() - 1);
            		}
            		Iterator<Map.Entry<Integer, Integer>> iter = map.entrySet().iterator();
            		while (iter.hasNext()) {
            			if (iter.next().getValue()  == 0) {
            				iter.remove();
            			}
            		}
                }

  • 0
    T

    What part of O(1) space did you not understand?
    my mistake


  • 0
    U

    His solution uses constant space, which is O(1). Only two values are ever in the majority map and result.


  • 0
    M

Log in to reply
 

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