如何從左到右和從右到左遍歷數組？

假設我有一個迫切的算法，保持兩個指數left和right和從左至右移動它們到右，從右到左如何從左到右和從右到左遍歷數組？

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

現在我想寫這個算法沒有可變指數。我該怎麼做？你有這種算法的例子嗎？我寧願採用非遞歸方法。

來源

2017-02-16 Michael

你可以使用遞歸的方法... –

哦，是的。謝謝。儘管如此，我寧願採用非遞歸方法。 – 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)

來源

2017-02-16 11:55:26 slouc

我喜歡使用'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可以隱式轉換爲。

來源

2017-02-16 20:54:21 Tim

這確實取決於每次迭代需要做什麼，但這裏有一些需要考慮的事情。

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不提供簡單/優雅的解決方案。

來源

2017-02-16 21:46:20 jwvh

如何從左到右和從右到左遍歷數組？

回答

相關問題