在排序的数组最长连续序列

本文介绍了在排序的数组最长连续序列的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

您给出数字Array，他们未排序/随机的顺序。你应该找到连续的数字阵列中的最长序列。注意该序列不必是该阵列中排序的顺序。下面是一个例子：

You are given an Array of numbers and they are unsorted/random order. You are supposed to find the longest sequence of consecutive numbers in the array. Note the sequence need not be in sorted order within the array. Here is an example :

输入：

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）的复杂性。

The solution needs to be of O(n) complexity.

据我所知，该解决方案包括使用一个哈希表，我也遇到过一些实现，使用2哈希表。一个无法排序，解决这一点，因为排序将需要O（nlgn），这是没有什么希望的。

I am told that the solution involves using a hash table and I did come across few implementations that used 2 hash tables. One cannot sort and solve this because sorting would take O(nlgn) which is not what is desired.

推荐答案

下面是使用只是一个单一的哈希集合，并没有做任何花哨的间隔合并Python中的解决方案。

Here is a solution in Python that uses just a single hash set and doesn't do any fancy interval merging.

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'