时间戳

首页 > 解决方案 > 如何找到序列的第二小的元素

scala - 如何找到序列的第二小的元素

问题描述

我找不到任何关于 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)insecondSmallest(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))
}

标签： scala

解决方案

又快又脏

list.distinct.sorted.lift(1)

该lift部分处理在 position 处没有条目的情况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]它在扫描序列时保留两个具有两个最大元素的 's。之所以Option[A]有效，是因为Ordering提供了一个隐式，它将 aNone作为底部元素连接到任何类型的排序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))是 ，这是不好的，因为有一个 Quick-Select 算法可以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)

推荐阅读