Given an array of size n, find the majority element. The majority element is the element that appears more than
You may assume that the array is non-empty and the majority element always exist in the array.
Example 1:
Example 2:
Solution
We can count frequency for the all elements and create a map of it. Iterate frequency map and select top most frequency element.
Code
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.util.HashMap; import java.util.Map; public class MajorityElements { public int majorityElement(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) { map.put(num, (map.getOrDefault(num, 0) + 1)); } int length = nums.length / 2, result = Integer.MIN_VALUE, freq = Integer.MIN_VALUE; for (int key : map.keySet()) { if (map.get(key) >= length && map.get(key) >= freq) { freq = map.get(key); result = key; } ; } return result; } public static void main(String[] args) { int[] nums= {2,2,1,1,1,2,2}; MajorityElements mjOnj=new MajorityElements(); System.out.println(mjOnj.majorityElement(nums)); } } |
Output
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.