Java HashMap, Sorting and Moore's majority vote solutions.


  • 11
    C
    public int majorityElement1(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num: nums) {
            if (map.containsKey(num))
                map.put(num, map.get(num) + 1);
            else
                map.put(num, 1);
            if (map.containsKey(num) && map.get(num) > nums.length/2)
                return num;
        }
        return -1;
    }
    
    public int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
    
    // Moore's majority vote method
    public int majorityElement(int[] nums) {
        int majority = 0;
        int count = 0;
        for (int num: nums) {
            if (count == 0)
                majority = num;
            if (num == majority)
                count ++;
            else 
                count--;
        }
        return majority;
    }

  • 0
    M

    if you sort length/2 times ,it may be faster.


  • 0
    G

    Don't you have to round up the majority? If you have an array [3, 3, 4] nums.length/2 will return 1 since Java rounds down for integer division.


Log in to reply
 

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