查找連續數字序列

如何查找數組數組中最長的連續數列？每個數組數組代表結果序列中的一個或零個數字。查找連續數字序列

實施例（[] - 表示陣列（像在JavaScript））：

[ 
    [1, 5, 6], 
    [7], 
    [22, 34], 
    [500, 550], 
    [60, 1], 
    [90, 100], 
    [243], 
    [250, 110], 
    [150], 
    [155], 
    [160] 
]

正確的輸出將是：[1, 7, 22, 60, 90, 110, 150, 155, 160]

詳細輸出：

1, -- index 1 all 1, 5 and 6 would match here, pick the smallest 
7, -- index 2 
22, -- index 3 
    -- index 4 skipped, the sequence would end here or wouldn't be the longest possible 
60, -- index 5 picked 60, because 1 wouldn't continue in the sequence 
90, -- index 6 
    -- index 7 skipped, the sequence would end here or wouldn't be the longest possible 
110, -- index 8 
150, -- index 9 
155, -- index 10 
160 -- index 11

來源

2011-10-31 Lukáš Novotný

你能解釋一下你是怎麼得到「正確的輸出」？我在這裏沒有看到任何模式... – NickLH

NickLH說什麼。 – Patrick87

@NickLH：看起來像最長的子序列，除了最多可以使用{1,5,6}中的一個，等等。 –

一種可能的方法是使用動態編程使用作爲參數的最後一個值和第一個子數組的索引來考慮。

這是基於與記憶化遞歸Python中的解決方案

data = [[1, 5, 6], 
     [7], 
     [22, 34], 
     [500, 550], 
     [60, 1], 
     [90, 100], 
     [243], 
     [250, 110], 
     [150], 
     [155], 
     [160]] 

def longest(x0, i, _cache=dict()): 
    if i == len(data): 
     return [] 
    try: 
     return _cache[x0, i] 
    except KeyError: 
     best = longest(x0, i+1) 
     for x in data[i]: 
      if x >= x0: 
       L = [x] + longest(x, i+1) 
       if len(L) > len(best): 
        best = L 
     _cache[x0, i] = best 
     return best 

print longest(0, 0)

來源

2011-10-31 15:33:29 6502

查找連續數字序列

回答

相關問題