2017-02-16 172 views
3

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

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

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

+2

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

+0

哦,是的。謝謝。儘管如此,我寧願採用非遞歸方法。 – Michael

+0

如果你想使用一個循環,你將不得不改變任何變量(至少一些helper變量),以獲得退出條件。順便說一句。你爲什麼不想使用遞歸?這是用不可變的值做功能的功能方式! (請更新您的問題) –

回答

4

您可以映射對你的清單,其反向之間的元素,再從左向右走經過數對列表,並繼續服用,只要你的條件滿足:

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) 
+0

我喜歡使用'reverse'的想法。但是它爲算法增加了一個數組傳遞。我想知道我是否可以使用'view/stream'來延遲'reverse'。 – Michael

+0

無論如何,就O(n)而言,就複雜性而言。這份名單真的很大嗎? – slouc

+0

@Michael:如果你想通過它們的索引訪問元素(比如在你的問題中的命令式版本),也許'val r = 0到(a.length - 1); val indices = r zip r.reverse; r.map {case(left,right)=> ...}'可能值得考慮? – Marth

2

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

1

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

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