我在一次采访中被问到这个问题。给定一个整数列表，我们如何找到其所有成员都在给定列表中的最大区间？
例如。给定列表 1,3,5,7,4,6,10 那么答案将是 [3, 7]。因为它具有 3 到 7 之间的所有元素。
我试图回答，但没有说服力。我采取的方法是首先对列表进行排序，然后检查最大间隔。但我被要求这样做O(n).
我知道一个基于散列和动态编程的解决方案。让f(x)是哈希函数。诀窍是哈希表值。考虑列表中包含的最长间隔，以 x 开头或结尾. Then h[f(x)] = y, where y is 该区间的另一端。请注意，该间隔的长度将是abs( x - y ) + 1。算法描述将清楚说明为什么要存储该值。
移至列表上。让i是当前索引，x:= 列表[i ]- 当前号码。现在
1. if h[f(x)]不为空，那么我们以前见过数字x。没什么可做的，继续。
2. Check h[f(x-1)] and h[f(x+1)].
2.1.如果它们都不为空，那就意味着我们已经见过面了x-1 and x+1，我们知道一些区间[a..x-1] and [x+1..b]我们已经在列表中见过了。我们知道这一点是因为a=h[f(x-1)] and b=h[f(x+1)]根据定义h。现在当我们得到x，这意味着我们现在已经满足了整个区间[a,b]，所以我们更新值如下：h[f(a)] := b and 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 and h[f(x)] := a.
2.3.如果它们都没有设置，那就意味着我们都没有遇到过x-1, nor x+1，并且最大区间包含x我们已经见过了是单身[x]本身。这样设置h[f(x)] := x.
最后，要得到答案，请跳过整个列表并采取maximum abs( x - h[f(x)] ) + 1对全部x.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
