<p>我只想实施一个“暴力”解决方案。。。在</p>
<ol>
<li>保留“当前序列”列表,最初为空</li>
<li>对于每个键,检查当前序列是否可以扩展一步。增加序列更新时也是目前为止最好的解决方案。在</li>
<li>对于未用于扩展序列的任何数字,请启动长度为1的新序列</li>
</ol>
<p>Python提供<code>set</code>这可能是一个合理的选择。。。这是一个示例实现:</p>
<pre><code>best = None
current_sequences = set()
last_key = None
for key in sorted(sequenceDict.keys()):
data = set(sequenceDict[key])
new_sequences = set()
if last_key == key-1:
# no gap in key value, may be some sequence got extended
for val, count in current_sequences:
if val+1 in data:
# found a continuation, keep this sequence
new_sequences.add((val+1, count+1))
data.remove(val+1)
if best is None or count+1 > best[0]:
# we've got a new champion
best = count+1, val+1, key
# add new sequences starting here
for v in data:
new_sequences.add((v, 1))
if best is None:
best = 1, v, key
current_sequences = new_sequences
last_key = key
</code></pre>
<p>一个棘手的部分是,如果键中有一个间隙,那么您就不能扩展序列,这就是<code>last_key</code>的用途。在</p>
<p>复杂性应该是<code>O(input_size × average_number_of_sequences)</code>。我只是一种直觉,但我想你不能再比这低了。我很想用<code>value - key</code>将一个常量与每个序列关联起来。。。然而,这不会检测到“间隙”(即键1中的值100和键3中的值102,但在键2中没有</strong>101的<strong>。在</p>
<p>对于输入的问题,解决方案是<code>(7, 735, 7)</code>,意思是一个7元素序列,在键7处以值735结尾。在</p>