一、問題描述
找出數(shù)組中出現(xiàn)次數(shù)最多的那個數(shù)适贸，要求時間復雜度和空間復雜度為O(n)黎侈。
二、實現(xiàn)思路
使用HashMap闷游，每個Entry的key存放數(shù)組中的數(shù)字峻汉，value存放該數(shù)字出現(xiàn)的次數(shù)，首先遍歷數(shù)組元素構造HashMap脐往，然后遍歷每個Entry休吠，找出最大value對應的key，即是出現(xiàn)次數(shù)最多的那個數(shù)业簿。
三瘤礁、代碼實現(xiàn)
package xzg.algorithm;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
/**
* 找出數(shù)組中出現(xiàn)次數(shù)最多的那個數(shù)--主元素問題
*/
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 的鏈表數(shù)組的結構<p/>
* 思路：<p/>
* 1.把數(shù)組中的每一個值，看做是HashMap中的 Key梅尤，第一次出現(xiàn)則把對應的Key的value設置為1（即出現(xiàn)一次）<p/>
* 2.后續(xù)則判斷以數(shù)組值為key柜思，是否在HashMap中存在岩调，若存在則對應的value加1，<p/>
* 3.重復步驟1和2,然后找到HashMap中value最大的鍵值對（此時：該value對應數(shù)組中數(shù)字出現(xiàn)大的重復次數(shù)赡盘，key則對應著值）<p/>
* HashMap中的Key就是數(shù)組中的值号枕，value即為該數(shù)值出現(xiàn)的次數(shù)<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++) {
//已數(shù)組中的值陨享，作為HashMap中的Key
int value = arr[i];
//判斷相關的key是否已存在
if (hashMap.containsKey(value)) {
//存在葱淳，則說明之前有出現(xiàn)過，則重復次數(shù)再次加1（對應的value加1）
int count = hashMap.get(value);
hashMap.put(value, count + 1);
} else {
//不存在抛姑，說明是第一次出現(xiàn)赞厕，則直接設置對應的value為1（value即表示該數(shù)值出現(xiàn)的次數(shù)）
hashMap.put(value, 1);
}
}
//已value創(chuàng)建集合
Collection<Integer> collection = hashMap.values();
//找到最大的值（即最大重復次數(shù)）
int maxCount = Collections.max(collection);
int maxNumber = 0;
for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
//循環(huán)遍歷，在HashMap中找到vmaxCount（最大重復次數(shù)）所對應的key（最大重復次數(shù)所對應的數(shù)值）
if (entry.getValue() == maxCount) {
maxNumber = entry.getKey();
}
}
System.out.println("出現(xiàn)次數(shù)最多的數(shù)字是：" + maxNumber);
System.out.println("該數(shù)字一共出現(xiàn)了：" + maxCount + " 次");
}
}
輸出結果如下：
出現(xiàn)次數(shù)最多的數(shù)字是：4
該數(shù)字一共出現(xiàn)了：3 次
Process finished with exit code 0
四定硝、算法分析
該算法時間復雜度為O(N)皿桑，空間復雜度為O(N)
五、總結
該問題需要了解HashMap相關的原理喷斋，可同時用來考察Java基礎和算法知識唁毒。
