это можно сделать в O (n * S) (n - количество входных строк, S - наибольший размер строки). Я дам вам общий алгоритм, в псевдокоде: Ява будет немного грязной ...
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), и его использование предотвратит O (nlogn) для других алгоритм сортировки или использование TreeSet
мы перебираем массив, размер которого не превышает n (если каждая страна появляется только один раз).
Трюк - это сортировка внутри цикла: это все равно O (n), потому что в общем случае вы сортируете не более n элементов (а не n элементов на одну итерацию!), Поэтому это O (2n) = O (n) ,
мы можем предварительно найти NumberOfElements за одну итерацию.
в целом: это O (n * S) , где n - количество входов (где заполняется arr), а S - наибольший размер строки (так как нам нужно прочитать струны ...)