scala - 具有最大元素的序列

Question

我有一个 Seq 和函数 Int => Int。我需要实现的是从原始 Seq 中仅获取那些等于结果序列最大值的元素(应用给定函数后我将拥有的元素):

def mapper:Int=>Int= x=>x*x
val s= Seq( -2,-2,2,2 )
val themax= s.map(mapper).max
s.filter( mapper(_)==themax)

但这似乎很浪费，因为它必须映射两次(一次用于过滤器，另一次用于最大值)。
有没有更好的方法来做到这一点？ (希望不使用循环)
编辑
此代码已被编辑；原来这是过滤器线: s.filter( mapper(_)==s.map(mapper).max) .如 om-nom-nom已经指出，这会评估`s.map(mapper).max 每次(过滤器)迭代，导致二次复杂度。

Answer 1

这是一个只进行一次映射并使用 `foldLeft' 函数的解决方案:

原则是遍历 seq 并且对于每个映射元素，如果它大于之前所有映射的元素，则用它开始一个新序列，否则如果相等，则返回所有最大值和新映射最大值的列表。最后，如果它小于则返回先前计算的最大值序列。

def getMaxElems1(s:Seq[Int])(mapper:Int=>Int):Seq[Int] = s.foldLeft(Seq[(Int,Int)]())((res, elem) => {
  val e2 = mapper(elem)
  if(res.isEmpty || e2>res.head._2) 
    Seq((elem,e2)) 
  else if (e2==res.head._2) 
    res++Seq((elem,e2)) 
  else res 
}).map(_._1) // keep only original elements

// test with your list
scala> getMaxElems1(s)(mapper)
res14: Seq[Int] = List(-2, -2, 2, 2)

//test with a list containing also non maximal elements
scala> getMaxElems1(Seq(-1, 2,0, -2, 1,-2))(mapper)
res15: Seq[Int] = List(2, -2, -2)

备注:关于复杂性

对于具有 N 个元素的列表，我上面介绍的算法的复杂度为 O(N)。然而:

映射所有元素的操作复杂度为 O(N)

计算最大值的操作复杂度为 O(N)

压缩操作的复杂度为 O(N)

根据最大值过滤列表的操作也是复杂度 O(N)

映射所有元素的操作复杂度为 O(M)，其中 M 为最终元素的数量

因此，最后您在问题中提出的算法与我的答案具有相同的复杂性(质量)，而且您提出的解决方案比我的更清楚。因此，即使 'foldLeft' 更强大，对于此操作，我会推荐您的想法，但压缩原始列表并仅计算一次 map (特别是如果您的 map 比简单的正方形更复杂)。这是在问题/聊天/评论中*scala_newbie* 的帮助下计算的解决方案。

def getMaxElems2(s:Seq[Int])(mapper:Int=>Int):Seq[Int] = {
  val mappedS = s.map(mapper) //map done only once 
  val m = mappedS.max         // find the max
  s.zip(mappedS).filter(_._2==themax).unzip._1
}

// test with your list
scala> getMaxElems2(s)(mapper)
res16: Seq[Int] = List(-2, -2, 2, 2)

//test with a list containing also non maximal elements
scala> getMaxElems2(Seq(-1, 2,0, -2, 1,-2))(mapper)
res17: Seq[Int] = List(2, -2, -2)