最有效的方式来通过订购频率字符串数组 [英] Most efficient way to order an array of Strings by frequency

问题描述

我有一个字符串数组：

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

什么是订购到一个较小的收藏的顺序是如何频繁的每个字符串与它的频率是多少？

What is the quickest/most efficient way to order this into a smaller Collection in order of how frequent each String is with its frequency?

不过，我觉得关于使用字符串作为一个键的HashMap＆LT;字符串，整数＆GT; ，但这不会是排序在频率方面

I though about using the String as a key in a HashMap<String,Integer> but this wouldnt be sorted in terms of frequency

我的另一种方法我认为是使用 TreeMap的＆LT;整数，字符串[]＆GT; 与该整数字符串列表，但似乎有很多检查涉及..

My other method i considered is using a TreeMap<Integer, String[]> with a list of Strings with that integer, but there seems a lot of checking involved..

我试着避免使用一个以上的循环，如果尽可能我的字符串数组会比上面那个大得多。谢谢！

Im trying to avoid using more than one loop If possible as my String arrays will be much larger than the one above. Thanks!

修改
我要的是只是为了能够输出字符串频率和$ P $秩序pferably能够配对的字符串，其阵列中的频率，因此，例如，两个输出数组：

EDIT What i want is just to be able to output the Strings in order of frequency and preferably be able to pair that String with its frequency in the array, So for example two output arrays:

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

这是一个非常简单的问题，如果速度wasnt一个问题，这就是为什么我问这里上伟大的思想家：）

This would be quite a simple problem if speed wasnt an issue which is why i ask the great minds on here :)

推荐答案

您可以分两步解决这个问题：

You can solve this in two steps:

1. 创建的计数的对象 - 一个地图＆LT;字符串，整数＆GT; 列出了每个字符串出现在的次数输入：换句话说，它是一个频率图。这是 O（N），因为你只需要一次遍历输入用于构建地图

1. Create a counter object - a Map<String, Integer> listing for each string the number of times it appears in the input: in other words, it's a frequency map. This is O(n), as you only need to traverse the input once for building the map

使用的previous地图，创建具有其密钥的列表，使用项的频率（在图中的值）作为排序标准进行排序。这是为O（n log n）的，并且可以调用 Col​​lections.sort（），以比较使用串频的比较

With the previous map, create a list with its keys, sorted using the frequency of items (the values in the map) as ordering criteria. This is O(n log n), and you can call Collections.sort(), with a Comparator that uses the string frequency for the comparisons

这是我的意思是：

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

以上code执行后，变量列表将包含以下值（相同频率的元素的顺序是不确定的）：

After the above code executes, the variable list will contain the following values (the order between elements of the same frequency is unspecified):

[x, y, a, z]

这是微不足道的列表转换为数组：

It's trivial to convert the list to an array:

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

如果你需要找出每个字符串的频率，只是遍历排序键：

And if you need to find out the frequency of each string, just iterate over the sorted keys:

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

这篇关于最有效的方式来通过订购频率字符串数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！