84669 人学习
152542 人学习
20005 人学习
5487 人学习
7821 人学习
359900 人学习
3350 人学习
180660 人学习
48569 人学习
18603 人学习
40936 人学习
1549 人学习
1183 人学习
32909 人学习
输入一个含有n个元素的数组,统计出其中众数及其出现次数,若是有多个众数的情况如何统计?
光阴似箭催人老,日月如移越少年。
雷雷
使用HashMap吧,key为数组元素,value为出现次数。每次put时,检查是否contain当前元素,包含的话,value+1,否则value=1
HashMap
key
value
使用 Map 来统计每个数出现的频率,然后按频率降序排序,选出频率最大的数即为众数(可能为多个)。
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; } }
这个是个经典的题目,是有时间复杂度是O(N)的做法的。代码网上有很多。我这里给一个链接。http://blog.csdn.net/hello2sy...
雷雷
使用
HashMap
吧,key
为数组元素,value
为出现次数。每次put时,检查是否contain当前元素,包含的话,value+1,否则value=1
使用 Map 来统计每个数出现的频率,然后按频率降序排序,选出频率最大的数即为众数(可能为多个)。
这个是个经典的题目,是有时间复杂度是O(N)的做法的。
代码网上有很多。我这里给一个链接。
http://blog.csdn.net/hello2sy...