Scala列表和拆分

我有一個家庭作業分配，它讓我們使用一個列表並將其分成兩部分，第一部分中的元素不大於p，第二部分中的元素大於p。所以它就像一個快速排序，除了我們不能使用任何排序。我真的需要一些關於如何去解決這個問題的提示。我知道即時通訊使用案例，但我不熟悉列表類如何在scala中工作。下面是我到目前爲止，但不知道如何去分裂2列表。Scala列表和拆分

使用

def split(p:Int, xs:List[Int]): List[Int] = { 

xs match { 
    case Nil => (Nil, Nil) 
    case head :: tail => 
}

來源

2014-11-15 zerocool 18

你明白算法嗎？ – justanothercoder

如果要遞歸執行此操作，請在函數內引入簽名splitHelper（p：Int，input：List，greater：List，noGreater：List）的幫助器函數：（List，List）。顯然列出[Int]無處不在。幫助函數只能調用自己或返回結果。通過調用實現你的主函數：splitHelper（p，xs，Nil，Nil） – ponythewhite

首先，你要split返回一對列表，因此，返回類型必須(List[Int], List[Int])。但是，一起使用對和列表通常意味着經常分解返回值。你可能想要有一個輔助功能爲你做繁重的工作。

例如，您的輔助功能可能會給出兩個列表，最初爲空，並建立內容，直到第一個列表爲空。結果將是這對清單。

在遞歸函數設計中，您必須決定的下一件事是「什麼是關鍵決策？」在你的情況下，它是「價值不大於p」。這導致以下代碼：

def split(p:Int, xs: List[Int]): (List[Int], List[Int]) = { 
    def splitAux(r: List[Int], ngt: List[Int], gt: List[Int]): (List[Int], List[Int]) = 
    r match { 
     case Nil => (ngt, gt) 
     case head :: rest if head <= p => 
     splitAux(rest, head :: ngt, gt) 
     case head :: rest if head > p => 
     splitAux(rest, ngt, head :: gt) 
    } 
    val (ngt, gt) = splitAux(xs, List(), List()) 
    (ngt.reverse, gt.reverse) 
}

倒車的步驟並不是嚴格必要的，但可能並不令人驚訝。同樣，第二個後衛謂詞明確了正在採取的路徑。

但是，有一種更簡單的方法：使用內置函數。

def split(p:Int, xs: List[Int]): (List[Int], List[Int]) = { 
    (xs.filter(_ <= p), xs.filter(_ > p)) 
}

filter只提取符合標準的項目。此解決方案遍歷列表兩次，但由於您在之前的解決方案中擁有reverse步驟，因此無論如何您都要這樣做。

來源

2014-11-15 13:20:54

爲什麼給出解決方案而不是幫助解決它？ – ponythewhite

如果內建函數被允許，還有一種更簡單的方法 - 使用'xs.partition（_ <= p）' –

Scala列表和拆分

回答

相關問題