Data Structure按值对元素进行排序

我需要一个Java中的数据结构，它可以操作String s，计算ArrayList<String>中每个单词的频率，然后我需要根据频率对它们进行排序。

简单地说，数据结构需要是一个关联数组，它可以被BY VALUES排序，我已经将行放入HashMap中，并对它不能被排序的事实感到惊讶，现在我一直在思考另一个数据结构。

p.S.(使用两个列表不适合我的程序，因为它需要进行大量计算，所以最好用一个结构来保存每个String及其出现，而不是String的列表和频率的其他列表(。

编辑：我很感激你的帮助，但有些人建议使用TreeMap，所以我想在这里指定一些内容：我需要根据字符串的出现次数排序的结构(在Map的情况下，应该是值而不是键(。

HashMap实际上没有排序，也不应该这样。如果您想对条目进行排序，可以使用SortedMap实现之一，例如TreeMap。

TreeMap有一个构造函数，它可以在有非标准Comparator的情况下帮助您(例如，如果您希望对String进行自然排序(：

TreeMap(Comparator<? super K> comparator)

UPD：我没有抓住要点，您需要按值对条目进行排序。

在这种情况下，我看不到任何解决方案，只有一种解决方案，即您只需要对条目进行几次排序，但不能保持这种状态。

您可以使用任何Map，例如，使用HashMap，但在处理之前，您可以对条目进行排序：

Set<Map.Entry<String, Integer>> entries = map.entrySet();
Set<Map.Entry<String, Integer>> sorted = new TreeSet<>(
        Comparator.comparingInt(Map.Entry::getValue).reversed()); // it's Java 8, but you may extract this lambda
sorted.addAll(entries);
for (Map.Entry<String, Integer> entry: sorted) {
    //...
    // the entries will be sorted by value
}

确切地说，你不能用任何类型的Map来维护以这种方式排序的条目，因为键的顺序只设置一次，你不能更改它，因为：

这不是常规的，Comparator/compareTo运算符应该在运行过程中给出相同的结果(这就是为什么可变类在Map中不受欢迎的原因(
这不会给您带来明显的结果，键通常不会重新排序

我认为没有简单的数据结构。

在收集频率数据时，频率会发生变化。对于哪个排序应该在收集所有字符串频率之后进行。

我能想到的最简单的方法是：

// psuedo-code
final Map<String, Integer> stringFreq = ....; // it doesn't matter what kind of impl you use
// collect the String vs frequency in stringFreq
Map<String, Integer> result = new TreeMap<String, Integer>(stringFreq, 
        new Comparator<String> {
        @Override
            public int compare(String a, String b) {
                int aFreq = stringFreq.get(a);
                int bFreq = stringFreq.get(b);
                return (aFreq==bFreq)?a.compareTo(b) : (aFreq-bFreq);
            }
        });

// result should have data sorted by frequency, and then the string value

Java有一个SortedMap接口，它有两个实现。最简单的是TreeMap

另一个解决方案，使用自定义bean和简单列表。

1/定义您的自定义bean

public class StringOccurence {
  String string ;
  int occurrence ;
}

2/创建一个比较器

public class StringOccurrenceComparator implements Comparator<StringOccurence> {
  @Override
  public int compare(StringOccurrence so1, StringOccurrence so2) {
    return Integer.compare(so1.occurrence, so2.occurrence);
  }
}

3/使用比较对您的列表进行排序

List<StringOccurrence> list = constructList();
Collections.sort(list, new StringOccurrenceComparator());

如果您很幸运地使用了java8，下面是第2点和第3点的简短版本：

List<StringOccurrence> list = constructList();
Collections.sort(list, (so1, so2) -> Integer.compare(so1.occurrence, so2.occurrence));

如果您使用maxheap数据结构来存储字符串及其频率出现值，并始终将最大值frequency保持在顶部，那么您只需一次性获得频率最大的字符串，但这里的复杂性是重新计算和调整最大堆，这实际上取决于你期望看到更多单词数量或单词频率高度变化的变化。

相关内容

最新更新

热门标签：