我在接受采访时被问到这个问题.给定一个整数列表,我们如何找到给定列表中所有成员的最大间隔？
例如,给出列表1,3,5,7,4,6,10然后回答是[3,7].因为它具有3到7之间的所有元素.
我试着回答,但我没有说服力.我采取的方法是先对列表进行排序,然后检查最大间隔.但我被要求这样做O(n).
Gri*_*yan 35
我知道基于散列和动态编程的解决方案.设f(x)为散列函数.诀窍是哈希表值.考虑列表中包含的最长间隔,该间隔以x开头或结尾.然后h [ f(x) ] = y,其中y是该区间的另一端.请注意,该间隔的长度将为abs(x-y)+ 1.算法描述将清楚说明存储该值的原因.
移动列表.设I为当前索引,x:= list [ i ] - 当前数字.现在
1.如果h [ f(x) ]不为空,那么我们之前已经遇到过数字x.无所事事,继续.
2.检查h [ f(x-1) ]和h [ f(x + 1) ].
2.1.如果它们都不是空的,那意味着我们已经遇到了x-1和x + 1,我们知道了一些间隔[ a..x-1 ]和[ x + 1..b ]我们已经在列表中见过面.我们知道,因为一个 = H [ F(X-1) ]和b = H [ F(X + 1) ]通过定义ħ.现在当我们得到x时,这意味着我们现在已经满足了整个区间[ a,b ],所以我们更新如下值:h [ f(a) ]:= b和 h [f(b)]:= a.
同时将h [ f(x) ]设置为某个值(让我们说x,而不是影响答案),只是为了下次我们在列表中遇到x时,我们忽略它.x已经完成了他的工作.
2.2.如果只设置其中一个,那么假设h [ f(x-1) ] = a,这意味着我们已经遇到了一些区间[ a..x-1 ],现在它用x扩展.更新将是h [ f(a) ]:= x和h [ f(x) ]:= a.
2.3.如果它们都没有设置,那意味着我们既没有遇到x-1,也没有遇到x + 1,而且我们已经遇到的包含x的最大区间是单个[ x ]本身.所以设h [ f(x) ]:= x.
最后,为了得到答案,传递整个列表并为所有x取最大 abs(x - h [ f(x) ])+ 1.
如果不希望排序,可以使用散列映射和Disjoint-set数据结构的组合.
对于列表中的每个元素,创建一个节点并使用key = element的值将其插入到哈希映射中.然后查询哈希映射的值+ 1和值-1.如果找到任何内容,请将当前节点与相邻节点所属的集合组合.完成列表后,最大集合对应最大间隔.
时间复杂度为O(N*α(N)),其中α(N)是逆Ackermann函数.
编辑:实际上,Disjoint-set对于这个简单的任务来说太强大了.Grigor Gevorgyan的解决方案不使用它.所以它更简单,更有效.
您可以通过权衡空间来获得线性时间.
列表中的第一步是线性的.最后一个是A的大小是线性的,如果你只有一些相距很远的值,它可能相对于你的列表很大.但是,既然你正在处理整体,那么A是有限的.
Too*_*eey -1
我想我会把它们排序到连续整数的列表中（假设每个数字只能出现一次）
取第一个数字
如果数字比现有列表中的数字低 1 或高 1？
是：在现有列表之前/之后
no ：创建一个以当前号码开头的新列表
如果还有更多数字，则返回顶部
显示最长的列表