java - 找出前N个最流行的元素

Question

我有一个 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
}

是否有更好、更干净/高效的方法来完成上述操作？

Answer 1

您要解决的问题是众所周知的 Selection algorithm , 特别是 - Quick select .虽然一般来说排序效果很好，但对于大型集合最好考虑这种方法，因为它会给你线性时间而不是 N*log(N)。