查找有它在列表中的所有成员在澳最大间隔(N) [英] Find the biggest interval that has all its members in list in O(n)
问题描述
我是在一次采访中问这个。鉴于整数列表,我们怎样才能找到具有其在给定列表中的所有成员的最大间隔时间?
I was asked this in an interview. Given a list of integers, How can we find the biggest interval that has all its members in the given list?
例如。定列表1,3,5,7,4,6,10那么答案将是[3,7]。因为它有3和7之间的所有元素
E.g. given list 1,3,5,7,4,6,10 then answer would be [3, 7]. Because it has all the elements between 3 and 7.
我想回答,但我是不能令人信服的。我采取的方法是首先对列表进行排序,然后检查它的最大间隔时间。但有人问我这样做 O(N)
I tried to answer but I wasn't convincing. The approach I took was to first sort the list and then check it for the biggest interval. But I was asked to do so in O(n)
.
推荐答案
我知道基于散列和动态规划的解决方案。让我们的的函数f(x)的是哈希函数。诀窍是哈希表值。考虑包含在列表中的的最长的间隔时间,无论是开始还是结束,其中x 的。然后点击 H [ F(X)的] = Y ,其中是是 该区间的另一端 。需要注意的是区间的长度将是 ABS(说明X - Y 的)+ 1 的。该算法描述清楚为什么要存储的值。
I know a solution based on hashing and dynamic programming. Let f(x) be the hash function. The trick is the hash-table value. Consider the longest interval contained in the list, which either starts or ends with x. Then h[f(x)] = y, where y is the other end of that interval. Note that length of that interval will be abs( x - y ) + 1. The algorithm description will make clear why to store that value.
动过名单。让我们的的我的是当前索引, X 的:=列表[我的] - 目前数。现在
Move over the list. Let i be current index, x := list[ i ] - current number. Now
1 如果 H [ F(X)的] 不为空,那么我们见过数x前。闲着没事,继续。
1. if h[f(x)] is not empty, then we've met number x before. Nothing to do, continue.
2 检查 H [ F(X-1)的] 和 H [ F(X + 1 )的] 。
2. Check h[f(x-1)] and 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)的] 按定义的 ^ h 。现在,当我们得到的的 X 的,这意味着我们现在已经达到了整个区间的 [ A,B 的] 所以我们更新值如下: H [ F(一)的]:= B 的和 H [ F(二)的]:=的在的。
同时将 H [ F(X)的] 以一定的价值(假设的的 X 的,不影响答案),只是让我们下一次见面的的 X 的在列表中,我们忽略它。 X 的已经完成了他的工作。
2.1. If they're both not empty, that means we've already met x-1 and x+1, and we know some intervals [a..x-1] and [x+1..b] which we've already met in the list. We know it because a=h[f(x-1)] and b=h[f(x+1)] by definition of h. Now when we got x, it means that we now have met the whole interval [a,b], so we update values as follows: h[f(a)] := b and h[f(b)] := a.
Also set h[f(x)] to some value (let's say x, not to impact the answer), just so that next time we meet x in the list, we ignore it. x has already done his job.
2.2 如果只有其中的设置,让我们说的 H [ F(X-1)的] =的在的,这意味着我们已经遇到过一些间隔 [ a..x-1 的] ,现在它的扩展是的 X 。更新将 H [ F(一)的]:= X 的和 H [ F(X)]:=的在的。
2.2. If only one of them is set, let's say h[f(x-1)] = a, that means we've already met some interval [a..x-1], and now it's extended with x. Update will be h[f(a)] := x and h[f(x)] := a.
2.3 如果他们没有设置,这意味着我们见过没有的的 X-1 的和 X + 1 的,以及包含的的 X 的我们已经见过的单一的 [ X <最大间隔/ EM>] 本身。因此,将 H [ F(X)的]:= X 的
2.3. If none of them is set, that means we've met neither x-1, nor x+1, and the biggest interval containing x we've already met is the single [x] itself. So set h[f(x)] := x.
最后,得到的答案,越过整个名单,并采取 最大的ABS( X 的 - H [ F(X))+ 1 的所有的的 X 的
Finally, to get the answer, pass over the whole list and take maximum abs( x - h[f(x)] ) + 1 for all x.
P.S。我熟悉这个问题,因为我一直在问它在采访中太:)
P.S. I'm familiar with this problem, because I've been asked it in the interview too :)
这篇关于查找有它在列表中的所有成员在澳最大间隔(N)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!