Problem Statement:
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Constraints:
- n == nums.length
- 1 <= n <= 5 * 104
- -109 <= nums[i] <= 109
Solution:
Algorithm:
- Initialize a HashMap with key and value as Integer.
- Iterate over the given input array.
- Adding elements to HashMap
- - If the element is already present in the HashMap, increment its count by 1
- - If the element is not present in the HashMap, add it to the HashMap with count 1
- Find the key with the highest value
- Iterate over the HashMap to find the key with the highest value
- If the value of the current key is greater than the value of the maxKey, update the maxKey
- Return the key with the highest value
Code:
public class Solution {
public int majorityElement(int[] nums) {
// 1. HashMap
HashMap<Integer, Integer> map = new HashMap<>();
//Adding elements to HashMap
for (int i = 0; i < nums.length; i++) {
// If the element is already present in the HashMap, increment its count by 1
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
}
// If the element is not present in the HashMap, add it to the HashMap with count 1
else {
map.put(nums[i], 1);
}
}
// 2. Find the key with the highest value
int max = 0;
int maxKey = 0;
// Iterate over the HashMap to find the key with the highest value
for (Integer key : map.keySet()) {
// If the value of the current key is greater than the value of the maxKey, update the maxKey
if (map.get(key) > max) {
max = map.get(key);
maxKey = key;
}
}
// Return the key with the highest value
return maxKey;
}
}
Top comments (0)