java - 按频率排序字符串数组的最有效方法

Question

我有一个字符串数组:

String[] stringArray = {"x", "y", "z", "x", "x", "y", "a"};

将其订购为较小的 Collection 的最快/最有效的方法是什么？按照每个String的频率顺序与它的频率有关吗？

我想使用 String作为 HashMap<String,Integer> 中的键但这不会按频率排序

我考虑的另一种方法是使用 TreeMap<Integer, String[]>带有该整数的字符串列表，但似乎涉及很多检查..

我尽量避免使用多个循环 如果可能的话，我的 String数组将比上面的大得多。谢谢!

编辑我想要的只是能够按频率顺序输出字符串，并且最好能够将该字符串与其在数组中的频率配对，例如两个输出数组:

["x", "y", "z", "a"]
[3,2,1,1]

如果速度不是问题，这将是一个非常简单的问题，这就是为什么我在这里请教伟大的思想:)

Answer 1

你可以分两步解决这个问题:

1. 创建一个计数器 对象 - Map<String, Integer>列出每个字符串在输入中出现的次数:换句话说，它是一个频率图。这是 O(n) ，因为您只需要遍历一次输入即可构建 map

2. 使用之前的 map ，创建一个带有键的列表，使用项目的频率( map 中的值)作为排序标准进行排序。这是 O(n log n) , 你可以调用 Collections.sort() , 与 Comparator使用字符串频率进行比较

这就是我的意思:

String[] stringArray = {"x", "y", "z", "x", "x", "y", "a"};

final Map<String, Integer> counter = new HashMap<String, Integer>();
for (String str : stringArray)
    counter.put(str, 1 + (counter.containsKey(str) ? counter.get(str) : 0));

List<String> list = new ArrayList<String>(counter.keySet());
Collections.sort(list, new Comparator<String>() {
    @Override
    public int compare(String x, String y) {
        return counter.get(y) - counter.get(x);
    }
});

上述代码执行后，变量list将包含以下值(相同频率的元素之间的顺序未指定):

[x, y, a, z]

将列表转换为数组很简单:

list.toArray(new String[list.size()])

如果您需要找出每个字符串的频率，只需遍历排序的键即可:

for (String str : list) {
    int frequency = counter.get(str);
    System.out.print(str + ":" + frequency + ", ");
}