系统会为您提供数字数组，它们是未排序/随机的顺序。您应该在数组中找到最长的连续数字序列。注意，序列不必在数组中按排序顺序排列。这是一个例子：
输入：
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），这不是期望的。
这是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'
