Как найти второй наименьший элемент последовательности

Question

Я не смог найти никакой документации по этому вопросу для Scala, но очень много для других языков программирования, которые никогда или редко используют рекурсию.

Последовательность должна быть пустой и содержать двойные числа.

val nonEmpthySeq = Seq(1,2,3,4,4,4,5,6,7,7,67,8,9,9,10)
val oneElementSeq = Seq(4)
val empthySeq = Seq()

Что я пробовал:

Я не могу написать ответ на этот вопрос, так как мой вопрос предположительно является дубликатом.

Использование сопоставления с образцом

def secondSmallest(xs: Seq[Int]): Option[Int] = xs match {
  case Nil => None
  case `xs` => Some(xs.distinct.sorted.apply(1))
}

сверхчистый однострочный

def secondSmallest(xs: Seq[Int]): Option[Int] =
    Try(xs.distinct.sorted.apply(1)).toOption

Оба возвращают

secondSmallest(nonEmpthySeq)
secondSmallest(oneElementSeq)
secondSmallest(empthySeq)

res0: Option[Int] = Some(2)
res1: Option[Int] = None
res2: Option[Int] = None

res1 объяснение:

x::Nil, для Seq(4) в secondSmallest(oneElementSeq) должно быть None, поскольку логически нет элемента второго по величине в списке, поэтому он должен быть None.

Если вам нужен один элемент в случае, если есть только один, вы должны обработать его с помощью case x :: Nil => Some(x).

def secondSmallest(xs: Seq[Int]): Option[Int] = xs match {
  case Nil => None
  case x :: Nil => Some(x)
  case `xs` => Some(xs.distinct.sorted.apply(1))
}

Answer 1

Быстро и грязно

list.distinct.sorted.lift(1)

Часть lift относится к случаю отсутствия входа в позицию 1.

---

Правильное линейное решение

Это работает в O(n), сканируя список ровно один раз:

def secondLargest[A: Ordering](as: Seq[A]): Option[A] = {
    val bottom = Option.empty[A]
    val ord = implicitly[Ordering[Option[A]]]
    import ord._
    as.foldLeft((bottom, bottom)) {
      case ((largest, second), x) =>
        val wrapped = Some(x)
        if (wrapped > largest) (wrapped, largest)
        else if (wrapped > second) (largest, wrapped)
        else (largest, second)
    }._2
}

Сохраняет два Option[A] с двумя самыми большими элементами при сканировании последовательности. Сравнение на Option[A] работает, потому что Ordering предоставляет неявный элемент, который примыкает None в качестве нижнего элемента к любому порядку типа A (для этого ord).

Пример:

println(secondLargest(Seq("foo", "bar", "baz")))
println(secondLargest(Seq(4, 7, 2, 5, 9, 6, 4)))

Печать:

// Some(baz)
// Some(7)

Обратите внимание, что все решения, основанные на активной сортировке, имеют как минимум O(n*log(n)), что не очень хорошо, поскольку существует алгоритм быстрого выбора, который может найти k -малый элемент в ожидаемом линейном времени.

---

Редактировать

О, хорошо ... Если вы хотите второе наименьшее , измените порядок в обратном порядке:

def secondSmallest[A: Ordering](as: Seq[A]): Option[A] =
  secondLargest(as)(implicitly[Ordering[A]].reverse)

println(secondSmallest(Seq("aa", "ca", "ab", "bc", "cc"))) // Some(ab)
println(secondSmallest(Seq(4, 7, 2, 5, 9, 6, 4)))          // Some(4)

Answer 2

ВНИМАНИЕ: обратите внимание на комментарий Андрея, прежде чем следовать за этим ответом.

---

Вот решение, которое я украл у Тима в комментариях:

def secondHighest(xs:Seq[Int]): Option[Int] = {
  xs.distinct.sorted.init.lastOption
}

и

def secondLowest(xs:Seq[Int]): Option[Int] = {
  xs.distinct.sorted.drop(1).headOption
}

Моя собственная ошибочная попытка была

Try(xs.distinct.sorted.apply(1)).toOption

Answer 3

со страницы PriorityQueue ScalaDocs :

Этот класс реализует приоритетные очереди с использованием кучи.

Со страницы Википедии в структуре данных кучи:

Структура данных Heap может использоваться для эффективного поиска k-го наименьшего (или самого большого) элемента в массиве.

В таком случае, возможно, мы сможем обобщить проблему, не жертвуя слишком большой эффективностью.

def fromTop[A:Ordering](xs :Seq[A], offset :Int) :Option[A] = {
  val pq = collection.mutable.PriorityQueue(xs:_*)
  for (_ <- 1 until offset) {
    val init = pq.headOption
    while (pq.nonEmpty && pq.head == init.get)
      pq.dequeue()
  }
  pq.headOption
}

def fromBottom[A:Ordering](xs :Seq[A], offset :Int) :Option[A] =
  fromTop(xs, offset)(implicitly[Ordering[A]].reverse)

Тестирование:

fromTop(Vector.empty[Int], 2)            //res0: Option[Int] = None
fromTop(Vector(9, 88), 0)                //res1: Option[Int] = Some(88)
fromTop(Vector('a','c','t','u','p'), 3)  //res2: Option[Char] = Some(p)

fromBottom(List(true,false,true), 2)     //res3: Option[Boolean] = Some(true)
fromBottom(List(1,2,3), 4)               //res4: Option[Int] = None
fromBottom(List(1,1,1,2,2,2,3,3,3), 2)   //res5: Option[Int] = Some(2)