scala 查找数组的最小和最大元素

Find min and max elements of array

提问by Rajeev

I want to find the min and max elements of an array using for comprehension. Is it possible to do that with one iteration of array to find both min element and max element?

我想找到用于理解的数组的最小和最大元素。是否可以通过一次数组迭代来找到最小元素和最大元素？

I am looking for a solution without using scala provided array.min or max.

我正在寻找不使用 Scala 提供的 array.min 或 max 的解决方案。

采纳答案by Yann Moisan

Here is a concise and readable solution, that avoids the ugly ifstatements :

这是一个简洁易读的解决方案，避免了丑陋的if陈述：

def minMax(a: Array[Int]) : (Int, Int) = {
  if (a.isEmpty) throw new java.lang.UnsupportedOperationException("array is empty")
  a.foldLeft((a(0), a(0)))
  { case ((min, max), e) => (math.min(min, e), math.max(max, e))}
}

Explanation : foldLeftis a standard method in Scala on many collections. It allows to pass an accumulator to a callback function that will be called for each element of the array.

说明：foldLeft是 Scala 中许多集合的标准方法。它允许将累加器传递给回调函数，该函数将为数组的每个元素调用。

Take a look at scaladocfor further details

查看scaladoc以获取更多详细信息

回答by Henri Hietala

You can get min and max values of an Array[Int] with reduceLeftfunction.

您可以使用reduceLeft函数获取 Array[Int] 的最小值和最大值。

scala> val a = Array(20, 12, 6, 15, 2, 9)

a: Array[Int] = Array(20, 12, 6, 15, 2, 9)

a: Array[Int] = Array(20, 12, 6, 15, 2, 9)

scala> a.reduceLeft(_ min _)

res: Int = 2

资源：整数 = 2

scala> a.reduceLeft(_ max _)

res: Int = 20

资源：整数 = 20

See this link for more information and examples of reduceLeftmethod: http://alvinalexander.com/scala/scala-reduceleft-examples

有关更多信息和reduceLeft方法示例，请参阅此链接：http: //alvinalexander.com/scala/scala-reduceleft-examples

回答by Shyamendra Solanki

def findMinAndMax(array: Array[Int]) = { // a non-empty array

    val initial = (array.head, array.head)  // a tuple representing min-max


    // foldLeft takes an initial value of type of result, in this case a tuple
    // foldLeft also takes a function of 2 parameters.
    // the 'left' parameter is an accumulator (foldLeft -> accum is left)
    // the other parameter is a value from the collection.

    // the function2 should return a value which replaces accumulator (in next iteration)
    // when the next value from collection will be picked.

    // so on till all values are iterated, in the end accum is returned.

    array.foldLeft(initial) { ((min, max), x) => 
          if (x < min) (x, max) 
          else if (x > max) (min, x) 
          else acc 
    }
}

回答by elm

Consider this (for non-empty orderable arrays),

考虑这个（对于非空的可排序数组），

val ys = xs.sorted
val (min,max) = (ys.head, ys.last)

回答by Jesper

val xs: Array[Int] = ???

var min: Int = Int.MaxValue
var max: Int = Int.MinValue

for (x <- xs) {
  if (x < min) min = x
  if (x > max) max = x
}

回答by DNA

Following on from the other answers - a more general solution is possible, that works for other collections as well as Array, and other contents as well as Int:

继其他答案之后 - 一个更通用的解决方案是可能的，它适用于其他集合以及Array其他内容以及Int：

def minmax[B >: A, A](xs: Iterable[A])(implicit cmp: Ordering[B]): (A, A) = {
  if (xs.isEmpty) throw new UnsupportedOperationException("empty.minmax")

  val initial = (xs.head, xs.head)

  xs.foldLeft(initial) { case ((min, max), x) => 
    (if (cmp.lt(x, min)) x else min, if (cmp.gt(x, max)) x else max) }
}                                               

For example:

例如：

minmax(List(4, 3, 1, 2, 5))              //> res0: (Int, Int) = (1,5)

minmax(Vector('Z', 'K', 'B', 'A'))       //> res1: (Char, Char) = (A,Z)

minmax(Array(3.0, 2.0, 1.0))             //> res2: (Double, Double) = (1.0,3.0)

(It's also possible to write this a bit more concisely using cmp.min()and cmp.max(), but only if you remove the B >: Atype bound, which makes the function less general).

（也可以使用cmp.min()and更简洁地编写它cmp.max()，但前提是您删除B >: A类型绑定，这会使函数不那么通用）。

回答by jlents

I'm super late to the party on this one, but I'm new to Scala and thought I'd contribute anyway. Here is a solution using tail recursion:

我参加这个聚会的时间非常晚，但我是 Scala 的新手，我认为无论如何我都会做出贡献。这是使用尾递归的解决方案：

@tailrec
def max(list: List[Int], currentMax: Int = Int.MinValue): Int = {
    if(list.isEmpty) currentMax
    else if ( list.head > currentMax) max(list.tail, list.head)
    else max(list.tail,currentMax)
}

回答by chaotic3quilibrium

Of all of the answers I reviewed to this questions, DNA's solution was the closest to "Scala idiomatic" I could find. However, it can be slightly improved by...:

在我对这些问题的所有回答中，DNA 的解决方案是我能找到的最接近“Scala 惯用语”的解决方案。但是，可以通过以下方式稍微改进...：

1. Performing as few comparisons as needed (important for very large collections)
2. Provide ideal ordering consistency by only using the Ordering.lt method
3. Avoiding throwing an Exception
4. Making the code more readable for those new to and learning Scala

1. 根据需要执行尽可能少的比较（对于非常大的集合很重要）
2. 仅使用 Ordering.lt 方法提供理想的排序一致性
3. 避免抛出异常
4. 使代码对于那些刚接触和学习 Scala 的人来说更具可读性

The comments should help clarify the changes.

注释应有助于澄清更改。

def minAndMax[B>: A, A](iterable: Iterable[A])(implicit ordering: Ordering[B]): Option[(A, A)] =
  if (iterable.nonEmpty)
    Some(
      iterable.foldLeft((iterable.head, iterable.head)) {
        case (minAndMaxTuple, element) =>
          val (min, max) =
            minAndMaxTuple //decode reference to tuple
          if (ordering.lt(element, min))
            (element, max) //if replacing min, it isn't possible max will change so no need for the max comparison
          else
            if (ordering.lt(max, element))
              (min, element)
            else
              minAndMaxTuple //use original reference to avoid instantiating a new tuple
      }
    )
  else
    None

And here's the solution expanded to return the lower and upper bounds of a 2d space in a single pass, again using the above optimizations:

这是扩展的解决方案，以在一次传递中返回 2d 空间的下限和上限，再次使用上述优化：

def minAndMax2d[B >: A, A](iterable: Iterable[(A, A)])(implicit ordering: Ordering[B]): Option[((A, A), (A, A))] =
  if (iterable.nonEmpty)
    Some(
      iterable.foldLeft(((iterable.head._1, iterable.head._1), (iterable.head._2, iterable.head._2))) {
        case ((minAndMaxTupleX, minAndMaxTupleY), (elementX, elementY)) =>
          val ((minX, maxX), (minY, maxY)) =
            (minAndMaxTupleX, minAndMaxTupleY) //decode reference to tuple
          (
              if (ordering.lt(elementX, minX))
                (elementX, maxX) //if replacing minX, it isn't possible maxX will change so no need for the maxX comparison
              else
                if (ordering.lt(maxX, elementX))
                  (minX, elementX)
                else
                  minAndMaxTupleX //use original reference to avoid instantiating a new tuple
            , if (ordering.lt(elementY, minY))
                (elementY, maxY) //if replacing minY, it isn't possible maxY will change so no need for the maxY comparison
              else
                if (ordering.lt(maxY, elementY))
                  (minY, elementY)
                else
                  minAndMaxTupleY //use original reference to avoid instantiating a new tuple
          )
      }
    )
  else
    None

回答by Vivek

scala> val v = Vector(1,2)
scala> v.max
res0: Int = 2
scala> v.min
res1: Int = 2

You could use the minand maxmethods of Vector

你可以使用min和max方法Vector

回答by Akos Krivachy

You could always write your own foldLeftfunction - that will guarantee one iteration and known performance.

您始终可以编写自己的foldLeft函数 - 这将保证一次迭代和已知性能。

val array = Array(3,4,62,8,9,2,1)
if(array.isEmpty) throw new IllegalArgumentException // Just so we can safely call array.head

val (minimum, maximum) = array.foldLeft((array.head, array.head)) {  // We start of with the first element as min and max
  case ((min, max), next) =>
    if(next > max) (min, next)
    else if(next < min) (next, max)
    else (min, max)
}

println(minimum, maximum) //1, 62