无序数组中的最长连续序列

Question

你有一个数字数组，这些数字是乱七八糟的，没有顺序。你的任务是找到这个数组中最长的连续数字序列。需要注意的是，这个序列在数组中不需要是按顺序排列的。举个例子：

输入：

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)。

有人告诉我，这个解决方案需要用到哈希表，我也看到了一些实现方法使用了两个哈希表。不能通过排序来解决这个问题，因为排序的复杂度是O(nlgn)，这不是我们想要的。

Answer 1

把所有东西放到一个哈希集合里。

然后遍历这个哈希集合。对于每一个元素，查看集合中与当前值相邻的所有值。记录下你能找到的最长序列，同时把找到的元素从集合中移除。保存这个序列的长度以便后续比较。

重复这个过程，直到哈希集合为空为止。

假设查找、插入和删除的时间都是O(1)，那么这个算法的时间复杂度就是O(N)。

伪代码：

 int start, end, max
 int temp_start, temp_end, count

 hashset numbers

 for element in array:
     numbers.add(element)

 while !numbers.empty():
     number = numbers[0]
     count = 1
     temp_start, temp_end = number 

     while numbers.contains(number - 1):
         temp_start = number - 1; count++
         numbers.remove(number - 1)

     while numbers.contains(number + 1):
         temp_end = number + 1; count++
         numbers.remove(number + 1)

     if max < count:
         max = count
         start = temp_start; end = temp_end

 max_range = range(start, end)

虽然里面的循环看起来不太好，但每个数字应该只用一次，所以时间复杂度应该是O(N)。

Answer 2

你可以有两个表：

• 开始表：包含（起始点，长度）
• 结束表：包含（结束点，长度）

当你添加一个新项时，你需要检查：

• 值加1在开始表中是否存在？如果存在，就把它删掉，然后创建一个新的项（值，当前长度加1）。同时，你还要在结束表中更新相同的结束点，但长度要增加。
• 值减1在结束表中是否存在？如果存在，就把它删掉，然后创建一个新的项（值，当前长度加1），这次要更新开始表（起始位置不变，但长度要增加）。

如果两个条件都成立，那么你实际上是在把两个已有的序列连接起来——用两个新的项替换掉四个旧的项，表示一个更长的序列。

如果两个条件都不成立，你就只需在两个表中各创建一个长度为1的新项。

在所有值都添加完后，你可以遍历开始表，找到值最大的那个键。

我觉得这样做是可行的，如果我们假设哈希查找/添加/删除的时间复杂度是O(1)，那么整体时间复杂度就是O(n)。

编辑：C#实现。这花了一些时间才搞定，但我觉得它有效 :)

using System;
using System.Collections.Generic;

class Test
{
    static void Main(string[] args)
    {
        int[] input = {10,21,45,22,7,2,67,19,13,45,12,
                11,18,16,17,100,201,20,101};

        Dictionary<int, int> starts = new Dictionary<int, int>();
        Dictionary<int, int> ends = new Dictionary<int, int>();

        foreach (var value in input)
        {
            int startLength;
            int endLength;
            bool extendsStart = starts.TryGetValue(value + 1,
                                                   out startLength);
            bool extendsEnd = ends.TryGetValue(value - 1,
                                               out endLength);

            // Stitch together two sequences
            if (extendsStart && extendsEnd)
            {
                ends.Remove(value + 1);
                starts.Remove(value - 1);
                int start = value - endLength;
                int newLength = startLength + endLength + 1;
                starts[start] = newLength;
                ends[start + newLength - 1] = newLength;
            }
            // Value just comes before an existing sequence
            else if (extendsStart)
            {
                int newLength = startLength + 1;
                starts[value] = newLength;
                ends[value + newLength - 1] = newLength;
                starts.Remove(value + 1);
            }
            else if (extendsEnd)
            {
                int newLength = endLength + 1;
                starts[value - newLength + 1] = newLength;
                ends[value] = newLength;
                ends.Remove(value - 1);
            }
            else
            {
                starts[value] = 1;
                ends[value] = 1;
            }
        }

        // Just for diagnostics - could actually pick the longest
        // in O(n)
        foreach (var sequence in starts)
        {
            Console.WriteLine("Start: {0}; Length: {1}",
                              sequence.Key, sequence.Value);
        }
    }
}

---

编辑：这里是用C#实现的单哈希集答案——我同意，这比上面的简单，但我保留我的原始答案以备后用：

using System;
using System.Collections.Generic;
using System.Linq;

class Test
{
    static void Main(string[] args)
    {
        int[] input = {10,21,45,22,7,2,67,19,13,45,12,
                11,18,16,17,100,201,20,101};

        HashSet<int> values = new HashSet<int>(input);

        int bestLength = 0;
        int bestStart = 0;
        // Can't use foreach as we're modifying it in-place
        while (values.Count > 0)
        {
            int value = values.First();
            values.Remove(value);
            int start = value;
            while (values.Remove(start - 1))
            {
                start--;
            }
            int end = value;
            while (values.Remove(end + 1))
            {
                end++;
            }

            int length = end - start + 1;
            if (length > bestLength)
            {
                bestLength = length;
                bestStart = start;
            }
        }
        Console.WriteLine("Best sequence starts at {0}; length {1}",
                          bestStart, bestLength);
    }
}

Answer 3

这里有一个用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'