Как найти студентов с лучшими оценками в списке?

Question

Предположим, у меня есть список Students. Students есть поля типа name, birth date, grade и т. Д. Как найти Students с лучшим grade в Scala?

Например:

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

Я хочу получить

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

Очевидно, я могу найти max grade («А» в списке выше), а затем 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 в конце.

Answer 2

Уже есть 6 ответов, но я все еще чувствую себя обязанным добавить свой дубль:

case class Lifted(grade: String, students: List[Student]) {
  def mergeBest(other: Lifted) = grade compare other.grade match {
    case  0 => copy(students = other.students ::: students)
    case  1 => other
    case -1 => this
  }
}

Этот небольшой класс дел поднимет Student в объект, который отслеживает лучшую оценку иячейка списка, содержащая студента.Это также учитывает логику слияния: если у нового учащегося есть

• такой же оценки => объединить нового учащегося в список результатов, с более коротким впереди для эффективности - иначе результатне будет O (n)
• более высокая оценка => заменить текущую лучшую оценку новым учеником
• более низкая оценка => сохранить текущую лучшую оценку

Результатзатем можно легко построить с помощью reduceLeft:

val result = { 
  list.view.map(s => Lifted(s.grade, List(s)))
    .reduceLeft((l1, l2) => l1.mergeBest(l2))
    .students
}
// result: List[Student] = List(Student(Paul,A), Student(Mike,A))

PS.Я поднимаю ваш вопрос - основываясь на количестве сгенерированных ответов

Answer 3

Используя foldLeft, вы просматриваете список студентов только один раз:

scala> students.foldLeft(List.empty[Student]) {
     | case (Nil, student) => student::Nil
     | case (list, student) if (list.head.grade == student.grade) => student::list
     | case (list, student) if (list.head.grade > student.grade) => student::Nil
     | case (list, _) => list
     | }
res17: List[Student] = List(Student(Paul,A), Student(Mike,A))

Answer 4

После сортировки вы можете использовать takeWhile, чтобы избежать повторения во второй раз.

case class Student(grade: Int)
val list = List(Student(1), Student(3), Student(2), Student(1), Student(25), Student(0), Student (25))

val sorted = list.sortWith (_.grade > _.grade)
sorted.takeWhile (_.grade == sorted(0).grade)

До сортировки взбитых сливок все еще сортируются, даже 1, 3, 0 и -1, которые нам не интересны, но это короткий код.

Обновление:

Второй подход, который может выполняться параллельно, состоит в том, чтобы разделить список и взять максимум каждой стороны, а затем только верхнюю, если есть, - и то и другое:

def takeMax (l: List[Student]) : List [Student] = l.size match {
    case 0 => Nil
    case 1 => l 
    case 2 => if (l(0).grade > l(1).grade) List (l(0)) else 
      if (l(0).grade < l(1).grade) List (l(1)) else List (l(0), l(1))
    case _ => {
      val left = takeMax (l.take (l.size / 2))
      val right= takeMax (l.drop (l.size / 2))
     if (left (0).grade > right(0).grade) left else 
     if (left (0).grade < right(0).grade) right else left ::: right }
}

Конечно, нам нравится выделять учащегося и метод сравнения двух из них.

def takeMax [A] (l: List[A], cmp: ((A, A) => Int)) : List [A] = l.size match {
    case 0 | 1 => l 
    case 2     => cmp (l(0), l(1)) match {
      case 0 => l 
      case x => if (x > 0) List (l(0)) else List (l(1))
    }
    case _ => {
      val left = takeMax (l.take (l.size / 2), cmp)
      val right= takeMax (l.drop (l.size / 2), cmp)
      cmp (left (0), right (0)) match {
        case 0 => left ::: right
        case x => if (x > 0) left else right }
     }
}

def cmp (s1: Student, s2: Student) = s1.grade - s2.grade 
takeMax (list, cmp) 

Answer 5

Вы можете использовать filter в списке студентов.

case class Student(grade: Int)
val students = ...
val minGrade = 5
students filter ( _.grade < minGrade)

Отлично работает и для типа String