高洛峰2017-04-18 10:54:53
for(int i=0;i<a.length;i++){
int count=0;
for(int j=0;j<a.length;j++){
if(a[i]==a[j])
count++;
System.out.println(a[i]+" "+count);
}
}
//这是最暴力的方法了吧,等我回去在写吧
ringa_lee2017-04-18 10:54:53
Use HashMap
吧,key
为数组元素,value
as the number of occurrences.
Every time you put, check whether it contains the current element. If it contains, value+1, otherwise value=1
怪我咯2017-04-18 10:54:53
Use Map to count the frequency of each number, then sort by frequency in descending order, and select the number with the highest frequency as the mode (it may be multiple).
import java.util.*;
public class What {
public static void main(String[] args) throws Exception {
int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 1, 2, 2, 3, 4, 5};
int n = arr.length;
List<Integer> modalNums = getModalNums(arr);
System.out.println(modalNums);
}
public static List<Integer> getModalNums(int[] arr) {
int n = arr.length;
if (n == 0) {
return Collections.EMPTY_LIST;
}
if (n == 1) {
return Arrays.asList(arr[0]);
}
Map<Integer, Integer> freqMap = new HashMap<>();
for (int i = 0; i < n; i++) { // 统计数组中每个数出现的频率
Integer v = freqMap.get(arr[i]);
// v == null 说明 freqMap 中还没有这个 arr[i] 这个键
freqMap.put(arr[i], v == null ? 1 : v + 1);
}
// 将 freqMap 中所有的键值对(键为数,值为数出现的频率)放入一个 ArrayList
List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(freqMap.entrySet());
// 对 entries 按出现频率从大到小排序
Collections.sort(entries, new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> e1, Map.Entry<Integer, Integer> e2) {
return e2.getValue() - e1.getValue();
}
});
List<Integer> modalNums = new ArrayList<>();
modalNums.add(entries.get(0).getKey()); // 排序后第一个 entry 的键肯定是一个众数
int size = entries.size();
for (int i = 1; i < size; i++) {
// 如果之后的 entry 与第一个 entry 的 value 相等,那么这个 entry 的键也是众数
if (entries.get(i).getValue().equals(entries.get(0).getValue())) {
modalNums.add(entries.get(i).getKey());
} else {
break;
}
}
return modalNums;
}
}
阿神2017-04-18 10:54:53
This is a classic question, and its time complexity is O(N).
There are many codes online. I'll give you a link here.
http://blog.csdn.net/hello2sy...