查找有它在列表中的所有成员在澳最大间隔（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屋！