java - 如何以最有效的方式获得以下输出？

Question

读取这种格式的文件:

japan
usa
japan
russia
usa
japan
japan
australia

按以下格式打印输出:

<country> : <count>

因此对于上述文件输出将是:

japan : 4
usa : 2
australia : 1
russia : 1

请注意，由于澳大利亚和俄罗斯的计数均为 1，因此名称排序为“a”在“r”之前。以最有效的方式去做。

这是我尝试过的:

Read the entire file and insert into a HashMap.
We will have pairs like <japan, 4> in there.
Now read the HashMap and insert in another TreeMap<Integer, List<String>>
Iterate over TreeiMap using a Comparator, which will iterate in reverse-sorted order.
Sort value (which will be a List<String>) and print the result.

Answer 1

这可以在O(n*S)中完成(n是输入字符串的数量，S是最大字符串大小)我会给你一个通用算法，用伪代码， Java 会有点困惑...

arr <- HashSet<String>[NumberOfElements]
map <- HashMap<String,int>
for each country:
   if country in map.keySet():
        count <- map.get(country)
        arr[count].del(country)
        map.delete(country)
        count <- count + 1
   else:
        count <- 1
   arr[count].add(country)  
   map.put(country,count)
for i=arr.length-1;i>=0;i--:
   sorted <- radixSort(arr[i])
   for each country in sorted:
      print country, i

这里的arr是一个“直方图”，因为每次迭代“大小”最多增加1，我们用它来存储数据。

复杂性解释:
该算法使用radix sort ，其中“数字”实际上是一个字符，并且时间复杂度为 O(n)，使用它将防止其他排序算法或使用 TreeSet 的 O(nlogn)
我们迭代最大大小为 n 的数组(如果每个国家只出现一次)。

一个技巧点是循环内的排序:它仍然是 O(n)，因为总的来说，您最多排序 n 个元素(而不是每次迭代 n 个元素!)，所以它是 O(2n)=O(n) 。
我们可以通过一次迭代预先找到 NumberOfElements。

总的来说:它是O(n*S)，其中n是输入的数量(填充arr)，S是最大的字符串大小(因为我们需要读取字符串...)