未排序数组中的最长连续序列

Question

这个问题已经在这里有了答案 ：

在数组中查找连续范围
（9个答案）

7年前关闭。

系统会为您提供数字数组，它们是未排序/随机的顺序。您应该在数组中找到最长的连续数字序列。注意，序列不必在数组中按排序顺序排列。这是一个例子：

输入：

A[] = {10,21,45,22,7,2,67,19,13,45,12,11,18,16,17,100,201,20,101}

输出为：

{16,17,18,19,20,21,22}

解决方案必须具有O（n）复杂度。

有人告诉我说该解决方案涉及使用哈希表，而我确实遇到了一些使用2个哈希表的实现。一个人不能排序和解决这个问题，因为排序将花费O（nlgn），这不是期望的。

Answer 1

这是Python中的解决方案，它仅使用单个哈希集，并且不执行任何花哨的间隔合并。

def destruct_directed_run(num_set, start, direction):
  while start in num_set:
    num_set.remove(start)
    start += direction
  return start

def destruct_single_run(num_set):
  arbitrary_member = iter(num_set).next()
  bottom = destruct_directed_run(num_set, arbitrary_member, -1) 
  top = destruct_directed_run(num_set, arbitrary_member + 1, 1)
  return range(bottom + 1, top)

def max_run(data_set):
  nums = set(data_set)
  best_run = []
  while nums:
    cur_run = destruct_single_run(nums)
    if len(cur_run) > len(best_run):
      best_run = cur_run
  return best_run

def test_max_run(data_set, expected):
  actual = max_run(data_set)
  print data_set, actual, expected, 'Pass' if expected == actual else 'Fail'

print test_max_run([10,21,45,22,7,2,67,19,13,45,12,11,18,16,17,100,201,20,101], range(16, 23))
print test_max_run([1,2,3], range(1, 4))
print max_run([1,3,5]), 'any singleton output fine'