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