查找前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
}

有没有更好的、更干净/高效的方法来完成上述任务呢？

- John Baum

---

使用 Collection.sort() 和自定义的 Comparator。 - user5156016

我会按照Jawad所说的去做，并在TrackDay类中添加一个totalTime()方法。 - phflack

@JawadLeWywadi 感谢您的建议。您能详细说明一下这样一个比较器如何与假设 TrackDay 不能在其定义中更改的情况下工作吗？提供一段代码片段将会非常有帮助。 - John Baum

Collections.sort(...) 的唯一问题是它会在原地进行排序，如果列表的顺序有意义，在排序操作之后将会丢失。 - TayTay

@Tgsmith61591 是的，我创建了一个临时列表，其中包含所有totalTimes值，并且临时列表已排序而不是原始列表。 - user5156016

Answer 1

你试图解决的问题被称为选择算法，特别是快速选择。虽然排序通常表现良好，但对于大型集合来说，考虑这种方法会更好，因为它可以在线性时间内完成，而不是N*log(N)。

- jdevelop

---

似乎快速选择算法是用于在列表中查找第k大的元素，而不是前k大的元素。您能否举个例子说明如何在这种情况下使用快速选择算法？ - John Baum

@JohnBaum 在列表中的前k个最大元素就是所有等于或大于第k个最大元素的元素。 - Klitos Kyriacou

这个答案很好。OP对创建一张天数和总时间的地图有正确的想法。但是如果你想要最佳性能，你应该使用这个算法而不是Java的sort()。后者会不必要地对整个列表进行排序，而不是只选择前N个。Java API没有部分排序函数，这真是遗憾；C++标准库有。 - Klitos Kyriacou

那么，在找到第k大的元素之后（比如说，如果我想要找到前三大的元素，那么就是第三大），我只需要循环遍历剩余的trackDays来找到那些大于第三大的元素吗？ - John Baum

不，当你找到第k大的元素时（枢轴将指向它）- 你需要从0迭代到K（K是枢轴的索引），并获取所有K个最大的项。请注意，它们可能不会按排序顺序出现 - 没有“合并”，只有“分区”，因此实际上并没有进行排序。 - jdevelop

如果你经常这样做，也许使用排序列表会更好。一旦你的列表被排序，复杂度就降到了O(1)。所以只有第一次是昂贵的。快速选择总是O(n)... - user5156016

Answer 2

这个解决方案应该是线性时间的。我假设startTimes和finishTimes支持随机访问。我不知道你的DateTime属于哪个API，所以我使用了java.time.LocalDateTime。

public List<TrackDay> findTop(List<TrackDay> trackDays, int limit) {
    limit = Math.min(limit, trackDays.size());
    List<Duration> durations = new ArrayList<>(Collections.nCopies(limit, Duration.ZERO));
    List<TrackDay> result = new ArrayList<>(Collections.nCopies(limit, null));
    int lastIndex = limit - 1;
    for (TrackDay trackDay : trackDays) {
        Duration duration = Duration.ZERO;
        for (int i = 0, n = trackDay.startTimes.size(); i < n; i++) {
            duration = duration.plus(Duration.between(trackDay.startTimes.get(i), trackDay.finishTimes.get(i)));
        }
        Integer destinationIndex = null;
        for (int i = lastIndex; i >= 0; i--) {
            if (durations.get(i).compareTo(duration) >= 0) {
                break;
            }
            destinationIndex = i;
        }
        if (destinationIndex != null) {
            durations.remove(lastIndex);
            result.remove(lastIndex);
            durations.add(destinationIndex, duration);
            result.add(destinationIndex, trackDay);
        }
    }
    return result;
}

- NorthernSky