一、问题描述
找出数组中出现次数最多的那个数，要求时间复杂度和空间复杂度为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基础和算法知识。
