Scala：查找子列表的最大元素

我需要編寫一個函數，它需要一個List[Int]，啓動索引和結束索引並返回該範圍內的最大元素。我有一個工作遞歸解決方案，但我想知道是否有可能使用Scala集合庫中的內置函數來完成它。Scala：查找子列表的最大元素

附加條件是：

1）O（N）運行時間 2）沒有中間結構創建 3）無可變數據結構

def sum(input:List[Int],startIndex:Int,endIndex:Int): Int = ???

來源

2014-04-01 Mansur Ashraf

是的，如果只有Scala API在List上帶有'max'函數......哦！等待！ – vptheron

我知道列表上的最大功能。它在子列表 –

上工作是的，如果你只能先切片，或創建一個「視圖」。從字面上看，您要求的所有內容都在「List」API頁面上。 http://www.scala-lang.org/api/current/index.html#scala.collection.immutable.List – vptheron

這是容易地與Scala的觀點：

def subListMax[A](list: List[A], start: Int, end: Int)(implicit cmp: Ordering[A]): A = 
    list.view(start, end).max

view不會創建的中間數據結構，它僅提供了一個接口到原來的切片。請參閱Scala集合庫的文檔中的Views chapter。

來源

2014-04-02 03:19:36 wingedsubmariner

我認爲這是不可能的您的標準。

沒有更高階的功能，我知道，它的工作列表的子列表。許多人只是創建中間集合。

這將是一個簡單的O(n)解決方案，但它會創建一箇中間結構。

input.slice(startIndex, endIndex + 1).max

當然還有函數，它們遍歷集合併產生一個值。示例是reduce和foldLeft。問題是他們遍歷整個集合，你不能設置開始或結束。

您可以從startIndex重複endIndex並使用foldLeft來通過索引獲取值。一個例子是：

(startIndex to endIndex).foldLeft(Integer.MIN_VALUE)((curmax, i) => input(i).max(curmax))

在這裏，我們只有一個迭代，這基本上行爲類似於for-loop並且不產生重中間集合。然而，從startIndex到endIndex的迭代是O(n)，並且在每次迭代中，我們都有一個索引操作（input(i)），其在List上通常也是O(n)。所以最後，sum不會是O(n)。

這當然只是我的經驗與斯卡拉，也許我誤入歧途。

啊和你的3）：我不確定你的意思。在函數內部使用可變狀態應該不是問題，因爲它只存在於計算結果然後消失。

來源

2014-04-01 23:52:55 Kigyo

Scala：查找子列表的最大元素

回答

相關問題