7

我有一个字符串数组：

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

Collection按照每个频率的频率顺序将其排序为更小的最快/最有效的方法String是什么？

我虽然关于在 a 中使用String作为键，HashMap<String,Integer>但这不会按频率排序

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

如果可能的话，我试图避免使用多个循环，因为我的String数组将比上面的数组大得多。谢谢！

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

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

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

4

7 回答 7

10

您可以分两步解决此问题：

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

  2. 使用之前的地图，创建一个包含其键的列表，使用项目的频率（地图中的值）作为排序标准进行排序。这是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 + ", ");
}
于 2013-09-06T14:58:26.557 回答
3

使用HashMap<String,Integer>来维护您的计数。这将是处理任意字符串列表的最有效方式。

ArrayList<Map.Entry<String,Integer>>从地图的entrySet().

Collections.sort()使用 a和自定义比较器对该列表进行排序。

不要沉迷于微优化。

于 2013-09-06T14:56:43.687 回答
2

如果第三方库是公平的游戏，那么以下使用 Guava 的单行代码是渐近最优的：

Multisets.copyHighestCountFirst(ImmutableMultiset.copyOf(array))
   .elementSet().toArray(new String[0]);
于 2013-09-06T16:41:49.403 回答
1 
String[] stringArray = {"x", "y", "z", "x", "x", "y", "a"};

List<String> list = Arrays.asList(stringArray);
Collections.sort(list);

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

for(int i = 0; i < list.size();) {

    String s = list.get(i); //get the string to count

    int count = list.lastIndexOf(s) - list.indexOf(s) + 1; //count it

    map.put(s, count); // add it

    i = list.lastIndexOf(s) + 1; // skip to the next string

}

我认为这是一个优雅的解决方案，但我不知道它的性能如何。如果你想使用 TreeMap 对其进行排序，但这真的很慢。

您可以在之后对其进行排序，如下所示：

TreeMap<String, Integer> sortedMap = new TreeMap<String, Integer>(unsortedMap);

但请注意，拥有Integer作为密钥是行不通的！因为a键是唯一的，如果例如a和b出现一次，a将被踢出！

于 2013-09-06T15:05:09.527 回答
1

打印结果： 1) 出现不同的字符串，按 desc 顺序排序。2) 出现相同的字符串，按 char 按 asce 顺序排序。 

 public static void sortStringByOccurance(String[] stringArray) {
    // O(n)
    Map<String, Integer> map = new HashMap<>();
    for (String str : stringArray) {
        map.put(str, map.containsKey(str)? map.get(str)+1 : 1);
    }

    // O(n)
    TreeMap<Integer, TreeSet<String>> treemap = new TreeMap<>();
    for (String key : map.keySet()) {
        if (treemap.containsKey(map.get(key))) {
            treemap.get(map.get(key)).add(key);
        }
        else {
            TreeSet<String> set = new TreeSet<>();
            set.add(key);
            treemap.put(map.get(key), set);
        }
    }

    // O(n)
    Map<Integer, TreeSet<String>> result = treemap.descendingMap();
    for (int count : result.keySet()) {
        TreeSet<String> set = result.get(count);
        for (String word : set) {
            System.out.println(word + ":" + count);
        }
    }
}
于 2015-08-12T22:21:15.550 回答
0

用最少的代码行是可能的：

String[] s = {"x", "y", "z", "x", "x", "y", "a"};
HashMap<String,Integer> hm = new HashMap<String,Integer>();
for(int i=0;i<s.length;i++){
    int count = hm.containsKey(s[i]) ? hm.get(s[i]) : 0;
    hm.put(s[i], count + 1);            
}
于 2021-07-26T11:34:35.640 回答
0

另一个解决方案：

String[] s = {"x", "y", "z", "x", "x", "y", "a"};
HashMap<String,Integer> hm = new HashMap<String,Integer>();

for(int i=0;i<s.length;i++){
    hm.putIfAbsent(s[i], 0);
    hm.put(s[i], hm.get(s[i]) + 1);
}
System.out.println(hm);
于 2021-07-26T14:31:24.853 回答