LeetCode - Algorithms - 169. Majority Element

There are many solutions to an easy problem.

Problem

169. Majority Element

Java

sorting

1
2
3
4
5
6
7
8
9
import java.util.*;

class Solution {
    public int majorityElement(int[] nums) {
        final int len = nums.length;
        Arrays.sort(nums);
        return nums[len >> 1];
    }
}

Submission Detail

  • 46 / 46 test cases passed.
  • Runtime: 1 ms, faster than 99.67% of Java online submissions for Majority Element.
  • Memory Usage: 42.9 MB, less than 72.59% of Java online submissions for Majority Element.

brute force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int majorityElement(int[] nums) {
        int half = nums.length >> 1;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i : nums) {
            Integer k = new Integer(i);
            if (map.containsKey(k)) {
                map.put(k, map.get(k)+1);
            }
            else {
                map.put(k, 1);
            }
        }
        int major = nums[0];
        for(Map.Entry<Integer, Integer> e : map.entrySet()) {
            if (e.getValue()>half) {
                major = e.getKey();
                break;
            }
        }
        return major;        
    }
}

Submission Detail

  • 46 / 46 test cases passed.
  • Your runtime beats 37.72 % of java submissions.
  • Your memory usage beats 14.52 % of java submissions.

Boyer-Moore Voting Algorithm

© Approach 6: Boyer-Moore Voting Algorithm

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int majorityElement(int[] nums) {
        int count=0;
        int candidate = nums[0];
        for(int num : nums) {
            if (count==0)
                candidate = num;
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;        
    }
}

Submission Detail

  • 46 / 46 test cases passed.
  • Runtime: 1 ms, faster than 99.67% of Java online submissions for Majority Element.
  • Memory Usage: 42.2 MB, less than 99.93% of Java online submissions for Majority Element.