无序数组中最长连续序列
本文关键字：连续 数组 无序 | 更新日期: 2023-09-27 18:09:05
给定一个未排序/随机顺序的数字数组。你应该找到数组中最长的连续数字序列。注意，序列不必在数组中按顺序排序。下面是一个例子:
输入:
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}
解复杂度为0 (n)。
我被告知解决方案涉及到使用一个哈希表，我确实遇到过一些使用两个哈希表的实现。我们不能排序并解决这个问题，因为排序需要O(nlgn)，这不是我们想要的。
可以有两个表:
- 起始表:(起始点，长度)
- 结束表:(End -point, length)
添加新项时，检查:
- 值+ 1是否存在于开始表中?如果是，则删除它并创建一个新的条目(value, length + 1)，其中length为"当前"长度。您还可以使用相同的端点更新结束表，但长度更大。
- 表尾是否存在value - 1 ?如果是，则删除它并创建一个新的条目(value, length + 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);
}
}
将所有内容转储到散列集
现在遍历哈希集。对于每个元素，查找与当前值相邻的所有值。跟踪您可以找到的最大序列，同时从集合中删除找到的元素。保存计数以便比较。
重复此操作，直到哈希集为空。
假设查找、插入和删除耗时为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)。
这是一个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'
另一个解决方案是哈希搜索，运行时间为O(n)
int maxCount = 0;
for (i = 0; i<N; i++)
{
// Search whether a[i] - 1 is present in the list.If it is present,
// you don't need to initiate count since it will be counted when
// (a[i] - 1) is traversed.
if (hash_search(a[i]-1))
continue;
// Now keep checking if a[i]++ is present in the list, increment the count
num = a[i];
while (hash_search(++num))
count++;
// Now check if this count is greater than the max_count got previously
// and update if it is
if (count > maxCount)
{
maxIndex = i;
count = maxCount;
}
}
实现如下:
static int[] F(int[] A)
{
Dictionary<int, int> low = new Dictionary<int, int>();
Dictionary<int, int> high = new Dictionary<int, int>();
foreach (int a in A)
{
int lowLength, highLength;
bool lowIn = low.TryGetValue(a + 1, out lowLength);
bool highIn = high.TryGetValue(a - 1, out highLength);
if (lowIn)
{
if (highIn)
{
low.Remove(a + 1);
high.Remove(a - 1);
low[a - highLength] = high[a + lowLength] = lowLength + highLength + 1;
}
else
{
low.Remove(a + 1);
low[a] = high[a + lowLength] = lowLength + 1;
}
}
else
{
if (highIn)
{
high.Remove(a - 1);
high[a] = low[a - highLength] = highLength + 1;
}
else
{
high[a] = low[a] = 1;
}
}
}
int maxLow = 0, maxLength = 0;
foreach (var pair in low)
{
if (pair.Value > maxLength)
{
maxLength = pair.Value;
maxLow = pair.Key;
}
}
int[] ret = new int[maxLength];
for (int i = 0; i < maxLength; i++)
{
ret[i] = maxLow + i;
}
return ret;
}
class Solution {
public:
struct Node{
int lower;
int higher;
Node(int l, int h):lower(l),higher(h){
}
};
int longestConsecutive(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
map<int,Node> interval_map;
map<int,Node>::iterator curr_iter,inc_iter,des_iter;
//first collect
int curr = 0;
int max = -1;
for(size_t i = 0; i < num.size(); i++){
curr = num[i];
curr_iter = interval_map.find(curr);
if (curr_iter == interval_map.end()){
interval_map.insert(make_pair(curr,Node(curr,curr)));
}
}
//the next collect
for(curr_iter = interval_map.begin(); curr_iter != interval_map.end(); curr_iter++)
{
int lower = curr_iter->second.lower;
int higher = curr_iter->second.higher;
int newlower = lower, newhigher = higher;
des_iter = interval_map.find(lower - 1);
if (des_iter != interval_map.end())
{
curr_iter->second.lower = des_iter->second.lower;
newlower = des_iter->second.lower;
}
inc_iter = interval_map.find(higher + 1);
if (inc_iter != interval_map.end()){
curr_iter->second.higher = inc_iter->second.higher;
newhigher = inc_iter->second.higher;
}
if (des_iter != interval_map.end()){
des_iter->second.higher = newhigher;
}
if (inc_iter != interval_map.end()){
inc_iter->second.lower = newlower;
}
if (curr_iter->second.higher - curr_iter->second.lower + 1> max){
max = curr_iter->second.higher - curr_iter->second.lower + 1;
}
}
return max;
}
};
这是Grigor Gevorgyan从这个问题的副本中得到的解决方案，但我认为简化了:
data = [1,3,5,7,4,6,10,3]
# other_sides[x] == other end of interval starting at x
# unknown values for any point not the end of an interval
other_sides = {}
# set eliminates duplicates, and is assumed to be an O(n) operation
for element in set(data):
# my intervals left hand side will be the left hand side
# of an interval ending just before this element
try:
left = other_sides[element - 1]
except KeyError:
left = element
# my intervals right hand side will be the right hand side
# of the interval starting just after me
try:
right = other_sides[element + 1]
except KeyError:
right = element
# satisfy the invariants
other_sides[left] = right
other_sides[right] = left
# convert the dictionary to start, stop segments
# each segment is recorded twice, so only keep half of them
segments = [(start, stop) for start, stop in other_sides.items() if start <= stop]
# find the longest one
print max(segments, key = lambda segment: segment[1] - segment[0])
这是基于Grigor Gevorgyan对类似问题的回答的python代码，我认为这是该问题的非常优雅的解决方案
l = [10,21,45,22,7,2,67,19,13,45,12,11,18,16,17,100,201,20,101]
d = {x:None for x in l}
print d
for (k, v) in d.iteritems():
if v is not None: continue
a, b = d.get(k - 1), d.get(k + 1)
if a is not None and b is not None: d[k], d[a], d[b] = k, b, a
elif a is not None: d[a], d[k] = k, a
elif b is not None: d[b], d[k] = k, b
else: d[k] = k
print d
m = max(d, key=lambda x: d[x] - x)
print m, d[m]
{2: 2, 67: None, 100: None, 101: None, 7: None, 201: None, 10: None, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: None, 101: None, 7: None, 201: None, 10: None, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 100, 101: None, 7: None, 201: None, 10: None, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: None, 201: None, 10: None, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: None, 10: None, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: None, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 10, 11: None, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 11, 11: 10, 12: None, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 12, 11: 10, 12: 10, 45: None, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 12, 11: 10, 12: 10, 45: 45, 13: None, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: None, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 16, 17: None, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 17, 17: 16, 18: None, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 18, 17: 16, 18: 16, 19: None, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 19, 17: 16, 18: 16, 19: 16, 20: None, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 20, 17: 16, 18: 16, 19: 16, 20: 16, 21: None, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 21, 17: 16, 18: 16, 19: 16, 20: 16, 21: 16, 22: None}
{2: 2, 67: 67, 100: 101, 101: 100, 7: 7, 201: 201, 10: 13, 11: 10, 12: 10, 45: 45, 13: 10, 16: 22, 17: 16, 18: 16, 19: 16, 20: 16, 21: 16, 22: 16}
16 22