如何从左到右和从右到左遍历数组？ [英] How to traverse array from both left to right and from right to left?

问题描述

假设我有一个命令式的算法，它保留了两个索引 left 和 right 并将它们从左向右移动，从右至左

Suppose I have an imperative algorithm that keeps two indices left and right and moves them from left to right and from right to left

var left  = 0
var right = array.length - 1
while (left < right) { .... } // move left and right inside the loop

现在我想写这个算法没有可变指标。
我该怎么做？你有这种算法的例子吗？我更喜欢非递归方法。

Now I would like to write this algorithm without mutable indices. How can I do that ? Do you have any examples of such algorithms ? I would prefer a non-recursive approach.

推荐答案

您可以映射列表与其相反的元素对，然后从

You can map pairs of elements between your list and its reverse, then go from left to right through that list of pairs and keep taking as long as your condition is satisfied:

val list = List(1, 2, 3, 4, 5)
val zipped = list zip list.reverse
val filtered = zipped takeWhile { case (a, b) => (a < b) }

过滤的值是 List（（1，5），（2，4））。
现在您可以对这些元素做任何您需要的操作：

Value of filtered is List((1, 5), (2, 4)). Now you can do whatever you need with those elements:

val result = filtered map {
  case (a, b) => 
    // do something with each left-right pair, e.g. sum them
    a + b
}

println(result) // List(6, 6)

如果您需要某种依赖于上下文的操作（也就是说，每个
迭代取决于前一个的结果），那么您必须使用
更强大的抽象（monad），但是如果
这对于你来说已经足够了，那么我们不要去那里。正如别人指出的那样，更好的办法就是简单地使用递归，但是你说这不是一个选项。

If you need some kind of context dependant operation (that is, each iteration depends on the result of the previous one) then you have to use a more powerful abstraction (monad), but let's not go there if this is enough for you. Even better would be to simply use recursion, as pointed out by others, but you said that's not an option.

编辑：

版本没有额外的通过换行，只有elem（长度 - 索引）的常量访问：

Version without extra pass for reversing, only constant-time access for elem(length - index):

val list = List(1, 2, 3, 4, 5)
val zipped = list.view.zipWithIndex
val filtered = zipped takeWhile { case (a, index) => (a < list(list.length - 1 - index)) }

println(filtered.toList)  // List((1, 0), (2, 1))

val result = filtered map {
  case (elem, index) => // do something with each left-right pair, e.g. sum them
    val (a, b) = (elem, list(list.length - 1 - index))
    a + b
}

println(result.toList) // List(6, 6)

这篇关于如何从左到右和从右到左遍历数组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！