用多個標準篩選列表的最佳選擇算法？

Question

我在Objective-C中進行編程，但語言不可知的答案在這裏可以正常工作。我有一個包含許多屬性的對象列表，包括創建日期和用戶GUID。我正在尋找一種合理有效的方式來過濾此列表，以僅包含來自每個用戶標識的最新條目。有沒有比O（n^2）更好的解決方案？我想我可以檢查每個元素，如果它是一個我尚未處理的ID，請抓住所有具有相同ID的對象，找到最近的對象，然後在其他位置存儲該值，但這似乎是一種天真的方法。

Answer 1

如果你只想擊敗O（n^2），那麼你可以按（ID，時間）進行排序，然後迭代並在第一次看到ID時將它附加到某個答案列表中。這將是O（n log n）。

或者，創建一個哈希表並遍歷列表。檢查項目是否在地圖中（按ID），如果是，則將其替換爲當前不常用的當前地圖。對於完美的散列函數，這將是O（n）。