找出数组中出现次数最多的那个数

一、问题描述

找出数组中出现次数最多的那个数，要求时间复杂度和空间复杂度为O(n)。

二、实现思路

使用HashMap，每个Entry的key存放数组中的数字，value存放该数字出现的次数，首先遍历数组元素构造HashMap，然后遍历每个Entry，找出最大value对应的key，即是出现次数最多的那个数。

三、代码实现

package xzg.algorithm;

import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;

/**
 * 找出数组中出现次数最多的那个数--主元素问题
 */
public class SearchMuch {

    public static void main(String[] args) {

        int[] arr = {4, 7, 1, 4, 9, 3, 2, 4, 15, 8, 6, 7, 3, 5, 10, 8};

        searchMuch(arr);
    }

    /**
     * 该算法是使用了 HashMap 的链表数组的结构<p/>
     * 思路：<p/>
     * 1.把数组中的每一个值，看做是HashMap中的 Key，第一次出现则把对应的Key的value设置为1（即出现一次）<p/>
     * 2.后续则判断以数组值为key，是否在HashMap中存在，若存在则对应的value加1，<p/>
     * 3.重复步骤1和2,然后找到HashMap中value最大的键值对（此时：该value对应数组中数字出现大的重复次数，key则对应着值）<p/>
     * HashMap中的Key就是数组中的值，value即为该数值出现的次数<p/>
     *
     * 时间复杂度为O(N)，空间复杂度为O(N)
     * @param arr
     */
    public static void searchMuch(int[] arr) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int length = arr.length;
        for (int i = 0; i < length - 1; i++) {
            //已数组中的值，作为HashMap中的Key
            int value = arr[i];
            //判断相关的key是否已存在
            if (hashMap.containsKey(value)) {
                //存在，则说明之前有出现过，则重复次数再次加1（对应的value加1）
                int count = hashMap.get(value);
                hashMap.put(value, count + 1);
            } else {
                //不存在，说明是第一次出现，则直接设置对应的value为1（value即表示该数值出现的次数）
                hashMap.put(value, 1);
            }
        }
        //已value创建集合
        Collection<Integer> collection = hashMap.values();
        //找到最大的值（即最大重复次数）
        int maxCount = Collections.max(collection);
        int maxNumber = 0;
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            //循环遍历，在HashMap中找到vmaxCount（最大重复次数）所对应的key（最大重复次数所对应的数值）
            if (entry.getValue() == maxCount) {
                maxNumber = entry.getKey();
            }
        }
        System.out.println("出现次数最多的数字是：" + maxNumber);
        System.out.println("该数字一共出现了：" + maxCount + " 次");

    }

}

输出结果如下：

出现次数最多的数字是：4
该数字一共出现了：3 次

Process finished with exit code 0

四、算法分析

该算法时间复杂度为O(N)，空间复杂度为O(N)

五、总结

该问题需要了解HashMap相关的原理，可同时用来考察Java基础和算法知识。