查找连续数字序列

问题描述：

如何查找数组数组中最长的连续数列？每个数组数组代表结果序列中的一个或零个数字。查找连续数字序列

实施例（[] - 表示阵列（像在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

你能解释一下你是怎么得到“正确的输出”？我在这里没有看到任何模式... – 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)

查找连续数字序列

相关推荐