根据元素出现的频率排列一个包含重复元素的列表

Question

如何根据列表中元素出现的频率安排列表中元素的顺序是一个好的方法（包括重复元素）.

我需要使用列表中出现频率最高的前5个项。

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

- Rajat Gupta

Answer 1

这个方法怎么样？

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

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()强制包装对列表的访问，并在其中封装地图更新逻辑。

- jmj

---

a) 这只有在多个对象是“相同”的情况下才起作用，而不是“相等”的情况下才起作用。 b) 它将计数保留在被计算的对象内。我认为这是糟糕的设计。一根香蕉不需要知道我冰箱里有多少根香蕉。 - Sean Patrick Floyd

@Jigar 好的，那么每当您放置或取出一个相等的对象时，您将不得不更新所有相等对象中的频率，这将增加比所需更多的复杂性。 - Sean Patrick Floyd

@Sean 如果我们使用 map（第二种方法），我们就不必这样做。而且，我们可以将“List”包装到某个类中，该类具有“add/removeFooTo/FromList()”，该类封装了逻辑。 - jmj

@Jigar 是的，如果您去掉第一种方法，我会点赞您的回答 :-) - Sean Patrick Floyd

@Jigar 好的，你抓住我了 :-) +1 - Sean Patrick Floyd

@Jigar 但是你知道使用Guava Multiset / Multimap，你可以免费获得这样的行为吗？ :-) - Sean Patrick Floyd

Answer 2

您可以使用Guava Multiset，并按频率排序。

---

关于性能，当然这取决于您有多少个不同的值，但是这段测试代码在我的机器上大约需要一秒钟。我认为对于10M个项目来说这是足够合理的。

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());
}

- Sean Patrick Floyd

Answer 3

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

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

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

---

更新：一个更简单的解决方案，时间复杂度相同。首先使用HashMap计算频率，然后将所有条目放入PriorityQueue并弹出五个值。 条目应该是值-频率对，可以通过频率进行比较（如@Jigar的解决方案）。 这样的排序不会“符合等式”（请参见Comparable的说明），但没关系。

- Bolo

---

听起来对我来说非常复杂。 - Sean Patrick Floyd

@Sean 如果你正在处理小列表，那么编写复杂的解决方案是不值得的。但是当你处理大列表（比如说，1000万个元素）时，你会注意到性能上的差异。 - Bolo

返回翻译文本：是的，但我建议使用Guava Multisets，它们是高度优化的数据结构，速度足够快（请参见我添加的代码）。 - Sean Patrick Floyd

@Sean 好的，它们可能足够快（我已经点赞了你的答案），但作为一名兼职理论计算机科学家，我不得不挑剔一下 ;) - Bolo

谢谢，但你必须意识到Guava的开发人员也是硬核计算机科学极客 :-) - Sean Patrick Floyd

Answer 4

我也会使用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");
}

- Thomas Mueller