Group список и отсортировать этот список по встречаемости в Java

Question

У меня есть большой список имен (первое имя и фамилия): Например:

{ john a, david x, marry u, john b, david y, john c}

Результат должен быть (сгруппированных по имени, упорядочено по частоте первого имени, не считая фамилию):.

john b 
john a 
john c 
david x 
david y 
marry u 

у меня есть довольно большой список (30M экземпляров), так что я должен учитывать сложность алгоритма.

Answer 1

Map<String, Integer> freq = new HashMap<String, Integer>(); 
for (String s: names): 
    first_name = Arrays.asList(s.split()).get(0).toLowerCase() 
    int count = freq.containsKey(name) ? freq.get(name) : 0; 
    freq.put(name, count + 1); 

Arrays.sort(names, new Comparator<String>() { 
    public int compare(String s1, String s2) { 
    int c = freq.get(Arrays.asList(s1.split()).get(0).toLowerCase()) - Arrays.asList(s2.split()).get(0).toLowerCase(); 
    return c; 
    } 
}); 

В основном создайте гистограмму частоты появления первых имен, а затем просто используйте ее как пользовательский компаратор.

Это всего две операции, поэтому вы ограничены сложностью самой сложной области проблемы, и поскольку генерация гистограммы является линейной, вы ограничены функцией сортировки, которая, как мне кажется, равна nlogn, что является лучшим, что вы можете делать с сортировкой.