根据出现频率排列列表中的元素（包含重复元素）

Question

根据列表中出现的频率来排列列表元素（具有重复元素）的好方法是什么？

我需要使用列表中最常出现的 5 个项目。

我正在考虑使用 HashMap 来计算元素的频率，方法是每次元素出现时增加相应的计数器。然后进行 HashMap 迭代 5 次以找到最高频率。每次迭代的元素。

Answer 1

您可以使用 番石榴 Multiset 和 按频率排序

---

关于性能。当然，这取决于您有多少个不同的值，但是这个测试代码在我的机器上花费了大约一秒钟。我想说这对于 1000 万个项目来说是足够合理的：

Multiset<Integer> set = HashMultiset.create();
int amount = 10000000;
Random random = new Random();
for (int i = 0; i < amount; i++) {
    set.add(Integer.valueOf(random.nextInt(255)));
}
TreeSet<Entry<Integer>> sortedEntries = Sets.newTreeSet(
        new Comparator<Entry<Integer>>() {
    public int compare(Entry<Integer> a, Entry<Integer> b) {
        return Ints.compare(a.getCount(), b.getCount());
    }
});
Iterables.addAll(sortedEntries, set.entrySet());
for (Entry<Integer> entry : Iterables.limit(sortedEntries, 5)) {
    System.out.println(entry.getElement());
}

Answer 2

任何基于比较的排序都会导致 O(N log N) 或更糟糕的时间复杂度，因此（渐近地）这些都不是好建议。

您的方法具有 O(N) 时间复杂度，这是您可以获得的最佳方法。您可以尝试降低常量（当前您对列表的元素进行大约 6*N 次访问）。

我会像这样进行两次迭代：首先使用 HashMap 计算频率。接下来，迭代映射中的条目并保留迄今为止看到的 5 个最常见值的有序 5 元素数组。对于每个新元素，检查该值是否比迄今为止第五个最常见的值更常见，并在必要时更新“前 5 个”。

---

更新一个更简单的解决方案，具有相同的时间复杂度。首先，使用 HashMap 计算频率。接下来，将所有条目放入 PriorityQueue< /code>并弹出五个值。这些条目应该是值-频率对，可按频率进行比较（如 @Jigar 的解决方案中所示）。这样的顺序不会“与 equals 一致”（请参阅​​ 类似的解释），但没关系。

Answer 3

我还会使用 HashMap。我找到了一些代码，我就是这么做的：

HashMap<String, Integer> counts = new HashMap<String, Integer>();

void increment(String s) {
    Integer oldCount = counts.get(s);
    if (oldCount == null) {
        counts.put(s, 1);
    } else {
        counts.put(s, oldCount + 1);
    }
}

列出元素：

Map.Entry<String, Integer>[] array = new Map.Entry[counts.size()];
counts.entrySet().toArray(array);
Arrays.sort(array, new Comparator<Map.Entry<String, Integer>>() {
    public int compare(Map.Entry<String, Integer> a, Map.Entry<String, Integer> b) {
        return b.getValue() - a.getValue();
    }
});
int x = 0, min = 0;
for (Map.Entry<String, Integer> el : array) {
    String k = el.getKey();
    println("Count: " + el.getValue() + "\n" + k + "\n\n");
}

Answer 4

这种方法怎么样？

维护一个包含计数的映射，

public static Map  <Foo,Integer>;

---

class Foo implements Comparator<Foo>{  
      private Bar element;


      public int compare(Foo f1, Foo f2){
       return SomeClass.map.get(f1) - SomeClass.map.get(f2);
      }

    }

只需使用 list 中的更新来更新映射。

使用 addFooToList() 、 removeFooFromList() 强制包装对 List 的访问，并封装其中的地图更新逻辑。