如何从左到右和从右到左遍历数组？

问题描述：

假设我有一个迫切的算法，保持两个指数left和right和从左至右移动它们到右，从右到左如何从左到右和从右到左遍历数组？

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

现在我想写这个算法没有可变指数。我该怎么做？你有这种算法的例子吗？我宁愿采用非递归方法。

你可以使用递归的方法... –

哦，是的。谢谢。尽管如此，我宁愿采用非递归方法。 – Michael

如果你想使用一个循环，你将不得不改变任何变量（至少一些helper变量），以获得退出条件。顺便说一句。你为什么不想使用递归？这是用不可变的值做功能的功能方式！（请更新您的问题） –

答

您可以映射对你的清单，其反向之间的元素，再从左向右走经过数对列表，并继续服用，只要你的条件满足：

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

的filtered值是List((1, 5), (2, 4))。现在你可以做任何你需要这些元素：

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），但是让我们不要去那里，如果这对你来说已经足够了。正如其他人指出的那样，更好的办法就是简单地使用递归，但是你说这不是一种选择。

编辑：

版本而无需额外的通逆转，只为ELEM固定时间的访问（长 - 指数）：

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)

我喜欢使用'reverse'的想法。但是它为算法增加了一个数组传递。我想知道我是否可以使用'view/stream'来延迟'reverse'。 – Michael

无论如何，就O（n）而言，就复杂性而言。这份名单真的很大吗？ – slouc

@Michael：如果你想通过它们的索引访问元素（比如在你的问题中的命令式版本），也许'val r = 0到（a.length - 1）; val indices = r zip r.reverse; r.map {case（left，right）=> ...}'可能值得考虑？ – Marth

答

使用reverseIterator：

scala> val arr = Array(1,2,3,4,5) 
arr: Array[Int] = Array(1, 2, 3, 4, 5) 

scala> arr.iterator.zip(arr.reverseIterator).foreach(println) 
(1,5) 
(2,4) 
(3,3) 
(4,2) 
(5,1)

此功能高效IndexedSeq集合，其中Array可以隐式转换为。

答

这确实取决于每次迭代需要做什么，但这里有一些需要考虑的事情。

array.foldRight(0){case (elem, index) => 
    if (index < array.length/2) { 
    /* array(index) and elem are opposite elements in the array */ 
    /* do whatever (note: requires side effects) */ 
    index+1 
    } else index // do nothing 
} // ignore result

上端：遍历数组只有一次，没有可变变量。

缺点：需要副作用（但在你的例子中就是暗示）。另外，如果它只遍历一半数组，它会更好，但这需要尽早突破，而且Scala不提供简单/优雅的解决方案。

如何从左到右和从右到左遍历数组？

相关推荐