169.多数元素
#java #leetcode #数组

问题语句:

给定一个大小n的数量,返回大多数元素。

大多数元素是出现超过N / 2次的元素。您可以假设大多数元素始终存在于数组中。

示例1:

输入: nums = [3,2,3]
输出: 3

示例2:
输入: nums = [2,2,1,1,1,1,2,2]
输出: 2

约束:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -10 <= nums [i] = 109

解决方案:
算法:

  • 初始化具有键和值的哈希图作为整数。
  • 迭代给定的输入数组。
  • 将元素添加到hashmap
  • - 如果该元素已经存在于哈希图中,请通过1
  • 将其计数增加
  • - 如果hashmap中不存在该元素
  • 找到具有最高值的键
  • 迭代哈希图以找到具有最高值的键
  • 如果当前密钥的值大于Maxkey的值,请更新Maxkey
  • 返回具有最高值的密钥

代码:

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;

    }

}