这是一个只进行一次映射并使用“foldLeft”函数的解决方案:
原则是遍历 seq,并且对于每个映射元素,如果它大于之前映射的所有元素,则使用它开始一个新序列,否则,如果它相等,则返回所有最大值的列表和新映射的最大值。最后,如果小于则返回先前计算的最大值 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”功能更强大,对于此操作,我也会推荐您的想法,但压缩原始列表并仅计算一次地图(特别是如果您的地图比简单的正方形更复杂)。这是在问题/聊天/评论中借助 *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)