我有幾個可變長度的陣列，其中填充了代表好資料塊和壞資料塊的元組。
input = [
[(True, 0, 400), (False, 400, 500), (True, 500, 1000)],
[(True, 0, 200), (False, 200, 400), (True, 400, 1000)],
[(False, 0, 100), (True, 100, 1000])]]
我想要做的是創建一個新的元組串列，表示在我的所有陣列中都很好的資料塊。以上結果如下。
output = [(False, 0, 500), (True, 500, 1000)]
每個原始陣列中的元組保證是交替的 True 和 False。每個陣列也將具有相同的開始和結束（在上述情況下為 0 和 1000）。
test = fn(input)
assert test == output
我的目標是在 O(n) 時間內完成這項作業，但我無法弄清楚。
uj5u.com熱心網友回復：
基本上，您想要合并陣列。您可以成對進行：首先，將第一個陣列與第二個陣列合并，然后將結果與第三個陣列合并，依此類推。
如何合并，兩個陣列？運行一個帶有兩個索引的回圈，當在第一個陣列上時，第二個在第二個陣列上。在每次回圈迭代中，您遞增一個索引，該索引表示具有較低資料位置的元組。然后你逐個元組合并陣列。
例如，讓我們考慮前兩個陣列。
[(True, 0, 400), (False, 400, 500), (True, 500, 1000)],
[(True, 0, 200), (False, 200, 400), (True, 400, 1000)],
我們從i指向(True, 0, 400)和j指向開始(True, 0, 200)。None 是假的，所以我們的輸出以(True, 0, 200)（這兩個元組的公共部分）開頭。然后我們遞增j（因為它的元組以 結尾200）。
在下一次迭代中i和分別j指向元組(True, 0, 400)和(False, 200, 400)。我們將它們合并，然后將(False, 200, 400)其添加到我們的輸出中。現在兩個元組都以相同的資料位置結束，所以我們都遞增。
接下來，我們得到元組(False, 400, 500)和(True, 400, 1000). 我們將它們合并以獲得(False, 400, 500). 因為我們輸出中的最后一個元組是False，而不是再添加一個False元組，我們只需將輸出中的最后一個元組擴展為500。我們增加i.
在最后一次迭代中，(True, 500, 1000)我們(True, 400, 1000)合并得到(True, 500, 1000).
因此，我們的輸出是[(True, 0, 200), (False, 200, 500), (True, 500, 1000)]。
uj5u.com熱心網友回復：
因此，您必須采用可能重疊的 False 范圍聯合。True 范圍可用于查找 0 - 1000。最后添加 True 范圍以填補空白。
....FFF...FFF...FFFFF.... old partial result, initially empty
......FFFFFFFFFFF.....F.. next input ranges
------------------------- union
....FFFFFFFFFFFFFFFFF.F.. new partial result
因此對輸入進行建模：
record Range(boolean onoff, int x1, int x2) { }
Range[][] input = {
{new Range(true, 0, 400), new Range(false, 400, 500), new Range(true, 500, 1000)},
{new Range(true, 0, 200), new Range(false, 200, 400), new Range(true, 400, 1000)},
{new Range(false, 0, 100), new Range(true, 100, 1000)}
}:
List<Range> accumulatedFalse new ArrayList<>();
for (Range[] ranges: input) {
int x0 = 0;
for (Range range: ranges) {
if (!range.onoff) {
// Accumulate this range:
... check for any overlapping and update accumulatedFalse
}
}
}
... Fill True ranges in the gaps ...
當然，我不會破壞編碼的樂趣。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/427020.html
上一篇：一列資料對最終分類結果的影響