java - 找到最流行的N个元素

我有一个TrackDay对象列表，供跑步者在不同日期绕田径运动。每对开始/结束时间表示跑步者单圈跑。我们保证有一个匹配的开始/结束日期(按照它们在相应列表中出现的顺序):

TrackDay() {
    List<DateTime> startTimes
    List<DateTime> finishTimes
}

我想找到跑步者最多的前N天(让我们说3天)。这意味着每个TrackDay对象找到N个最长的总开始/结束时间。天真的方法是执行以下操作:

for (TrackDay td : listOftrackDays) {
    // loop through each start/finish lists and find out the finish-start time for each pair.
    // Add the delta times (finish-start) up for each pair of start/finish objects.
    // Create a map to store the time for each TrackDay
    // sort the map and get the first N entries
}

是否有更好，更干净/有效的方法来完成上述工作？

最佳答案

您要解决的问题众所周知为Selection algorithm，尤其是Quick select。虽然排序通常效果很好，但对于大型集合，最好考虑采用这种方法，因为它将给您线性时间而不是N * log(N)。