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...