如何在列表中找到成绩最好的学生？

Question

假设,我有一份清单Students.Students有像田name,birth date,grade等你将如何找到Students最好的grade斯卡拉？

例如:

List(Student("Mike", "A"), Student("Pete", "B"), Student("Paul", A))"

我想得到

List(Student("Mike", "A"), Student("Paul", A))

显然,我可以找到max grade(上面列表中的"A")然后filter列表

students.filter(_.grade == max_grade)

此解决方案仅O(N)在列表上运行两次.你能提出更好的解决方案吗？

Answer 1

在列表上运行两次可能是最好的方法,但如果你坚持只运行一次的解决方案,你可以使用折叠(这里适用于空列表):

(List[Student]() /: list){ (best,next) => best match {
  case Nil => next :: Nil
  case x :: rest =>
    if (betterGrade(x,next)) best
    else if (betterGrade(next,x)) next :: Nil
    else next :: best
}}

如果您不熟悉折叠,请在此处的答案中对其进行描述.当你通过一个集合(例如列表)时,它们是积累某些东西的一般方式.如果你不熟悉匹配,你可以用isEmpty和做同样的事情head.如果您希望学生的顺序与原始列表中的顺序相同,请.reverse在最后运行.