leetcode169:多数元素

package com.mxnet;

import java.util.HashMap;
import java.util.Set;

public class Solution169 {

    public static void main(String[] args) {

    }

    /**
     * 给定一个大小为 n 的数组nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 n/2 的元素。
     * <p>
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素
     *
     * @param nums
     * @return
     * 思路：
     * 1. 使用hashmap集合
     * 2. key保存不重复元素，value保存出现的次数
     * 3. 扫描一边数组所有元素，将其映射到hash 集合中
     * 4. 遍历hash集合，找到出现次数大于 n / 2的key返回
     */
    public int majorityElement(int[] nums) {
        //创建hashmap集合，key保存不重复数字，value保存数字出现的次数
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        //将数组中的元素全部映射到hashmap中
        for (int num : nums) {
            //若该元素已经出现过，则将其对应的value+1
            if (hashMap.containsKey(num)) {
                hashMap.put(num, hashMap.get(num) + 1);
            } else {
                //若元素第一次出现，则保存到hash集合中，出现次数为1
                hashMap.put(num, 1);
            }
        }
        //遍历hash集合，找到出现次数大于 n / 2的，返回其key
        Set<Integer> keySet = hashMap.keySet();
        for (Integer key : keySet) {
            if (hashMap.get(key) > nums.length / 2) {
                return key;
            }
        }
        return 0;
    }

}