如何在功能合併從列表

我有多少，我需要合併，這樣的範圍，對象，所有的重疊範圍消失了重疊號，範圍：如何在功能合併從列表

case class Range(from:Int, to:Int) 

val rangelist = List(Range(3, 40), Range(1, 45), Range(2, 50), etc)

這裏是範圍：

一旦完成後，我們會得到：

1 50 
70 90 
100 200

勢在必行算法：

Pop（）第一個range-obj並遍歷列表的其餘部分，並將其與其他每個範圍進行比較。
如果有重疊的項目，將它們合併在一起（這會產生一個新的Range實例），並從源列表中刪除2個合併候選項。
在列表的末尾添加Range對象（可能已經通過合併多次更改）到最終結果列表中。
對剩下的項目中的下一項重複此操作。
一旦源列表爲空，我們就完成了。

要做到這一點勢在必行必須創造了很多臨時變量，索引循環等。

所以我不知道是否有一個功能更強大的方法呢？

初看起來，源代碼集合必須能夠像Stack一樣提供pop（）PLUS ，使其能夠在遍歷它時通過索引刪除項目，但是那樣就不再那麼實用了。

來源

2012-02-09 recalcitrant

嘗試尾遞歸。（如果沒有發生尾遞歸優化，則需要註釋纔會發出警告;編譯器會在沒有註釋的情況下執行此操作）

import annotation.{tailrec => tco} 
@tco final def collapse(rs: List[Range], sep: List[Range] = Nil): List[Range] = rs match { 
    case x :: y :: rest => 
    if (y.from > x.to) collapse(y :: rest, x :: sep) 
    else collapse(Range(x.from, x.to max y.to) :: rest, sep) 
    case _ => 
    (rs ::: sep).reverse 
} 
def merge(rs: List[Range]): List[Range] = collapse(rs.sortBy(_.from))

來源

2012-02-09 23:26:12

假定'rs'按範圍初始元素排序。最好是讓'x包含y.from'。 – 2012-02-10 04:58:27

'merge'排序並傳遞給'collapse'。如果你不這樣做，你的運行時間應該是'O（n^2）'而不是'O（n log n）'。 – 2012-02-10 05:43:52

呃！我沒有注意到'merge'方法... – 2012-02-10 15:33:46

我喜歡這些類型的謎題：

case class Range(from:Int, to:Int) { 
    assert(from <= to) 

    /** Returns true if given Range is completely contained in this range */ 
    def contains(rhs: Range) = from <= rhs.from && rhs.to <= to 

    /** Returns true if given value is contained in this range */ 
    def contains(v: Int) = from <= v && v <= to 
} 

def collapse(rangelist: List[Range]) = 
    // sorting the list puts overlapping ranges adjacent to one another in the list 
    // foldLeft runs a function on successive elements. it's a great way to process 
    // a list when the results are not a 1:1 mapping. 
    rangelist.sortBy(_.from).foldLeft(List.empty[Range]) { (acc, r) => 
    acc match { 
     case head :: tail if head.contains(r) => 
     // r completely contained; drop it 
     head :: tail 
     case head :: tail if head.contains(r.from) => 
     // partial overlap; expand head to include both head and r 
     Range(head.from, r.to) :: tail 
     case _ => 
     // no overlap; prepend r to list 
     r :: acc 
    } 
    }

來源

2012-02-09 21:53:34 leedm777

非常感謝。你需要在將它恢復到排序順序之後進行反轉。 – monkjack 2013-11-22 19:13:44

這裏是我的解決方案：

def merge(ranges:List[Range]) = ranges 
    .sortWith{(a, b) => a.from < b.from || (a.from == b.from && a.to < b.to)} 
    .foldLeft(List[Range]()){(buildList, range) => buildList match { 
    case Nil => List(range) 
    case head :: tail => if (head.to >= range.from) { 
     Range(head.from, head.to.max(range.to)) :: tail 
    } else { 
     range :: buildList 
    } 
    }} 
    .reverse 

merge(List(Range(1, 3), Range(4, 5), Range(10, 11), Range(1, 6), Range(2, 8))) 
//List[Range] = List(Range(1,8), Range(10,11))

來源

2012-02-09 21:57:36

如何在功能合併從列表

回答

相關問題