具有最大元素的Seq-Java 学习之路

我有一个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)

但这似乎很浪费，因为它必须映射两次（一次用于过滤器，另一次用于最大值） . 有一个更好的方法吗？（希望没有使用循环）

EDIT 该代码已被编辑;在原来这是过滤线： s.filter( mapper(_)==s.map(mapper).max) . 正如om-nom-nom指出的那样，这会对每个（过滤器）迭代的`s.map（mapper）.max进行求值，从而导致二次复杂度 .

1 回答

3
这是一个只使用`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)
```
Remark: 关于复杂性

对于具有N个元素的列表，上面给出的算法具有O（N）的复杂度 . 然而：
- 映射所有元素的操作具有复杂度O（N）
- 计算最大值的操作是复杂度O（N）
- 压缩操作的复杂度为O（N）
- 根据max过滤列表的操作也是复杂度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)
```
回复于 2024-05-05T18:42:26+08:00

具有最大元素的Seq

1 回答

相关问题