从计数谈起 在漫长的求职刷 leetcode 的过程中，会遇到一个普遍的情景，但是苦于所学的语言没有封装数据结构去描述这一情景，所以一直以来都是自己在代码里实现。直到某一天看到关于 hyperloglog 的算法，才发现本问题比想象的要复杂得多，那就是计数的问题。 所谓计数，用来统计一个集合中出现的各个不同元素的个数，由于在 leetcode 中太普遍，以至于一时间没有找到什么特别有代表性的问题可以贴在这里，但是普遍情况下使用 HashMap 实现，例如： class Counter<T>{ private HashMap<T, Integer> countMap; public Counter<T>(){ HashMap<T, Integer> countMap = new HashMap(); } public void add(T t){ countMap.put(this.get(t) + 1); } public int get(T t){ return countMap.getOrDefault(t, 0); } } 如果计数类型是正整数，还可以考虑直接用 Index 数组计数，即数组的 Index 为计数的元素，但是前提是元素不能太大。 class Counter{ private int[] countMap; public Counter(int … Continue reading “HyperLogLog 算法（一）——Bitmap 与 LinearCounting”
1 Comment so far