用多个标准筛选列表的最佳选择算法？

Question

我在Objective-C中进行编程，但语言不可知的答案在这里可以正常工作。我有一个包含许多属性的对象列表，包括创建日期和用户GUID。我正在寻找一种合理有效的方式来过滤此列表，以仅包含来自每个用户标识的最新条目。有没有比O（n^2）更好的解决方案？我想我可以检查每个元素，如果它是一个我尚未处理的ID，请抓住所有具有相同ID的对象，找到最近的对象，然后在其他位置存储该值，但这似乎是一种天真的方法。

Answer 1

如果你只想击败O（n^2），那么你可以按（ID，时间）进行排序，然后迭代并在第一次看到ID时将它附加到某个答案列表中。这将是O（n log n）。

或者，创建一个哈希表并遍历列表。检查项目是否在地图中（按ID），如果是，则将其替换为当前不常用的当前地图。对于完美的散列函数，这将是O（n）。