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

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)复杂度.

我被告知解决方案涉及使用哈希表,我确实遇到了几个使用2个哈希表的实现.人们无法对此进行排序和解决,因为排序将需要O(nlgn),这不是所期望的.

Answer 1

你可以有两个表:

• 开始表:(起点,长度)
• 结束表:(结束点,长度)

添加新项目时,您将检查:

• start table中是否存在值+ 1？如果是,则删除它并创建一个新值(value,length + 1),其中length是"当前"长度.您还要使用相同的终点更新结束表,但更长.
• 结果表中是否存在值-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 2

将所有内容转储到哈希集.

现在浏览一下hashset.对于每个元素,查找与当前值相邻的所有值的集合.跟踪您可以找到的最大序列,同时删除从集合中找到的元素.保存计数以进行比较.

重复此操作,直到hashset为空.

假设查找,插入和删除是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)

嵌套的while看起来不漂亮,但每个数字只能使用一次,所以应该是O(N).

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'