找到最受歡迎的N個元素

我有一個TrackDay對象的列表，用於跑步者在不同的日子裏繞着田徑場奔跑。每對開始/結束時間表示跑步者單圈跑。我們保證不存在（它們出現在相應的列表的順序）匹配的開始/結束日期：找到最受歡迎的N個元素

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 
}

有沒有更好的，更乾淨/有效的方式來做到上述？

來源

2015-11-05 John Baum

使用Collection.sort（）和自定義比較器。 – 2015-11-05 16:25:03

我願意做Jawad說的話，並在'TrackDay'類中添加'totalTime（）'方法 – phflack

@JawadLeWywadi感謝您的建議。你能否擴展一下這個比較器的工作原理，TrackDay的定義是不能改變的。一個代碼片段將極大地幫助 –

您試圖解決的問題衆所周知爲Selection algorithm，特別是 - Quick select。雖然排序總的來說效果很好，但對於大型集合來說，考慮這種方法會更好，因爲它會給你線性時間而不是N * log（N）。

來源

2015-11-05 18:23:30 jdevelop

看起來，快速選擇是爲了在列表中找到第k個最大值，而不是列表中的第k個最大值。你能舉一個例子說明在這種情況下如何使用快速選擇？ –

@JohnBaum列表中最大的第一個k就是所有那些等於或大於第k個最大元素的元素。 –

這個答案是一個很好的答案。 OP有創建天和總時間圖的正確理念。但是如果你想要最好的性能，那麼你應該使用這個算法，而不是Java的sort（）。後者將不必要地對整個列表進行排序，而不是隻選擇前N個。令人遺憾的是，Java API沒有部分排序功能; C++標準庫有。 –

該解決方案應該是線性時間。我假定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; 
}

來源

2015-11-05 20:56:44 NorthernSky

找到最受歡迎的N個元素

回答

相關問題