输入一个含有n个元素的数组,统计出其中众数及其出现次数,若是有多个众数的情况如何统计?
光阴似箭催人老,日月如移越少年。
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); } } //这是最暴力的方法了吧,等我回去在写吧
使用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...