java - 对列表进行分组并按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这是您可以用排序做的最好的。