如何找到一个数组中的众数？

Question

输入一个含有n个元素的数组，统计出其中众数及其出现次数，若是有多个众数的情况如何统计？

Answer 1

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);
}
}
//这是最暴力的方法了吧，等我回去在写吧

Answer 2

使用HashMap吧，key为数组元素，value为出现次数。
每次put时，检查是否contain当前元素，包含的话，value+1，否则value=1

Answer 3

使用 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;
    }
}

Answer 4

这个是个经典的题目，是有时间复杂度是O(N)的做法的。
代码网上有很多。我这里给一个链接。
http://blog.csdn.net/hello2sy...

Answer 5

用两个hash表，可以把事件复杂度降到O(N):

function zhongshu(arr) {

  var itemToCount = {};
  var countToItems = {};

  var max = 0;

  arr.forEach(item => {
    if (itemToCount[item] === void 0) {
      itemToCount[item] = 0;
    }
    let count = ++itemToCount[item];
    if (!countToItems[count]) countToItems[count] = [];
    max = Math.max(count, max);
    countToItems[count].push(item);
  });
  // return Object.keys(itemToCount).filter(x => itemToCount[x] === max).map(x => x | 0);
  return countToItems[max];
}

Answer 6

java8:

    public static <T> T getModeFromValueList(@NotNull List<T> valueList) {
        return valueList
                .stream()
                .filter(Objects::nonNull)
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
                .entrySet()
                .stream()
                .max((Comparator.comparingLong(Map.Entry<T, Long>::getValue)))
                .map(Map.Entry::getKey)
                .orElse(null);
    }