查找O（n）中列出所有成员的最大间隔

我在接受采访时被问到了这个问题。 给定一个整数列表，我们如何find给定列表中所有成员的最大间隔？

例如，给出列表1,3,5,7,4,6​​,10然后回答将是[3,7]。 因为它具有3到7之间的所有元素。

我试图回答，但我没有说服力。 我采取的方法是首先sorting列表，然后检查它的最大间隔。 但是我被要求在O(n)这样做 。

Answer 1

我知道一个基于哈希和dynamic编程的解决scheme。 设f（x）是哈希函数。 诀窍是哈希表值。 考虑列表中包含的最长时间间隔，它以x开始或结束 。 那么h [ f（x） ] = y ，其中y是该间隔的另一端 。 请注意，该间隔的长度将是abs（ x – y ）+ 1 。 algorithm描述将明确为什么要存储该值。

移到列表中。 让我成为当前索引， 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的定义， a = 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 。

PS我很熟悉这个问题，因为我在面试中也被问到了:)

Answer 2

如果sorting不可取，则可以使用哈希映射和不相交集数据结构的组合 。

对于列表中的每个元素，创build一个节点并使用key = element的值将其插入散列映射中。 然后查询哈希映射值+ 1和值-1。 如果发现任何东西，则将当前节点与相邻节点所属的集合相结合。 当完成列表时，最大的集合对应于最大的区间。

时间复杂度为O（N *α（N）），其中α（N）为逆阿克曼函数。

编辑：实际上，对于这个简单的任务，Disjoint-setfunction太强大了。 Grigor Gevorgyan的解决scheme不使用它。 所以它更简单，更高效。

Answer 3

你可以换取空间来获得线性时间。

1. 扫描列表中的最小值和最大值S和L.
2. 使用一组布尔值或一个位vectorA，足够大以容纳（L – S + 1）条目。
3. 再次浏览列表，当你看到它的时候，把A的适当元素设置为true。
4. 现在，A被sorting。 经过A并find最大的连续的真值。

你的列表中的第一步是线性的。 最后一个是A的大小是线性的，如果你只有几个相距很远的值，那么相对于你的列表可能是很大的。 但是，既然你在处理整数，A是有界的。

Answer 4

1个想法 ：好吧，我认为你必须有点sorting清单，但你不能合并或快速sorting。 但是，如果你有记忆，你可以使用从整数计数sorting的想法。

所以你可以创build0和1的数组，从0到最大的int值，然后填充它，如果你有值，然后find最大连续数组

2想法 ：创build值的字典，查找最小和最大 – 所有O（N）操作：

 dict = {1: 1, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 10: 10} min = 1 max = 10 

那么，就像i in range(min, max) ，并find最长的连续子集

 >>> d = [1, 3, 5, 7, 4, 6, 10] >>> s = set(d) >>> mind = min(d) >>> maxd = max(d) >>> a, b, j = 0, 0, 0 >>> for i in range(mind, maxd): if i not in s: if (b - a) < (i - j - 1): a, b = j, i - 1 j = i + 1 >>> a, b (3, 7) 

但对于像[1, 9000, 100000]这样的稀疏列表，这可能会很慢。

编辑 ：基于Grigor Gevorgyan的超级伟大的答案，这里是Python的O（N）字典解决scheme的代码（我只是喜欢它的简单！

 l = [1, 3, 5, 7, 4, 6, 10] 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] 

输出：

 {1: None, 3: None, 4: None, 5: None, 6: None, 7: None, 10: None} {1: 1, 3: None, 4: None, 5: None, 6: None, 7: None, 10: None} {1: 1, 3: 3, 4: None, 5: None, 6: None, 7: None, 10: None} {1: 1, 3: 4, 4: 3, 5: None, 6: None, 7: None, 10: None} {1: 1, 3: 5, 4: 3, 5: 3, 6: None, 7: None, 10: None} {1: 1, 3: 6, 4: 3, 5: 3, 6: 3, 7: None, 10: None} {1: 1, 3: 7, 4: 3, 5: 3, 6: 3, 7: 3, 10: None} {1: 1, 3: 7, 4: 3, 5: 3, 6: 3, 7: 3, 10: 10} 3 7 

Answer 5

我使用HashSet制作了一个非常简单的解决scheme。 由于contains和remove是O（1）操作，因此您可以简单地从随机设置项目中创build一个新的时间间隔，并“扩大”它的时间间隔，直到您发现其全部大小，随着时间的推移从该集合中移除项目。 删除是关键，因为这是阻止你“重复”任何间隔。

这可能有助于以这种方式思考 – 列表中有K个间隔，其大小合计为N.然后，您的任务是发现这些间隔是什么，而不重复任何间隔或项目。 这就是为什么HashSet是完美的工作 – 当你扩大你的时间间隔，你可以有效地从集合中删除项目。 那么你所要做的就是跟踪最大的时间间隔。

1. 把列表放入一个HashSet
2. 虽然这个集合是非空的，
   1. 从集合中随机移除一个项目
   2. 从该项目定义新的时间间隔
   3. 展开时间间隔如下：
      1. 定义i = interval.start-1
      2. 当集合包含i ，从集合中删除i ，并减lessi和interval.start
      3. 在另一个方向重复步骤2（从interval.end扩展）
   4. 如果扩展的间隔大于以前的最大间隔，则logging新的间隔作为最大的间隔
3. 返回最大间隔

以下是Java中的解决scheme：

 public class BiggestInterval { static class Interval { int start; int end; public Interval(int base) { this(base,base); } public Interval(int start, int end) { this.start = start; this.end = end; } public int size() { return 1 + end - start; } @Override public String toString() { return "[" + start + "," + end + "]"; } } /** * @param args */ public static void main(String[] args) { System.out.println(biggestInterval(Arrays.asList(1,3,5,7,4,6,10))); } public static Interval biggestInterval(List<Integer> list) { HashSet<Integer> set = new HashSet<Integer>(list); Interval largest = null; while(set.size() > 0) { Integer item = set.iterator().next(); set.remove(item); Interval interval = new Interval(item); while(set.remove(interval.start-1)) { interval.start--; } while(set.remove(interval.end+1)) { interval.end++; } if (largest == null || interval.size() > largest.size()) { largest = interval; } } return largest; } } 

Answer 6

考虑使用平均O（1）哈希表构build的字典，这将是线性的。

 L = [1,3,5,7,4,6,10] a_to_b = {} b_to_a = {} for i in L: if i+1 in a_to_b and i-1 in b_to_a: new_a = b_to_a[i-1] new_b = a_to_b[i+1] a_to_b[new_a] = new_b b_to_a[new_b] = new_a continue if i+1 in a_to_b: a_to_b[i] = a_to_b[i+1] b_to_a[a_to_b[i]] = i if i-1 in b_to_a: b_to_a[i] = b_to_a[i-1] a_to_b[b_to_a[i]] = i if not (i+1 in a_to_b or i-1 in b_to_a): a_to_b[i] = i b_to_a[i] = i max_a_b = max_a = max_b = 0 for a,b in a_to_b.iteritems(): if ba > max_a_b: max_a = a max_b = b max_a_b = ba print max_a, max_b 

Answer 7

这里有一个类似于Grigor的解决scheme。 两个主要的区别在于，这个解决scheme存储顺序集的长度而不是其他索引，并且这消除了最后的哈希集迭代的需要。

1. 遍历数组

   • 通过查找和更新相邻的设置端点来构build一个哈希映射：

     键 – 数组值

     值 – 当密钥是连续集的端点时，存储该集的长度。 否则，保持真实，所以你只考虑一次。

   • 如果当前设置的尺寸最长，则更新最长设置尺寸和最长设置开始。

下面是一个清晰的JavaScript实现，以及一个小工具来看它的行动：

 var array = [1,3,5,7,4,6,10]; //Make a hash of the numbers - O(n) assuming O(1) insertion var longestSetStart; var longestSetSize = 0; var objArray = {}; for(var i = 0; i < array.length; i++){ var num = array[i]; if(!objArray[num]){//Only consider numbers once objArray[num] = 1;//Initialize to 1 item in the set by default //Get the updated start and end of the current set var currentSetStart = num;//Starting index of the current set var currentSetEnd = num;//Ending index of the current set //Get the updated start of the set var leftSetSize = objArray[num - 1]; if(leftSetSize){ currentSetStart = num - leftSetSize; } //Get the updated end of the set var rightSetSize = objArray[num + 1]; if(rightSetSize){ currentSetEnd = num + rightSetSize; } //Update the endpoints var currentSetSize = currentSetEnd - currentSetStart + 1; objArray[currentSetStart] = currentSetSize; objArray[currentSetEnd] = currentSetSize; //Update if longest set if(currentSetSize > longestSetSize){ longestSetSize = currentSetSize; longestSetStart = currentSetStart; } } } var longestSetEnd = longestSetStart + longestSetSize - 1; 

Answer 8

诀窍是把这些项目看作是一个集合，而不是一个列表。 这使您可以识别连续范围的开始或结束的项目，因为一个集合可以让您检查item-1或item + 1是否存在。 这样，你就可以在线性的时间和空间里解决问题。

伪代码：

• 枚举集合中的项目，查找位于范围起始处的项目（当x-1不在集合中时，x开始一个范围）。
• 对于每个范围的起始值，向上扫描，直到find范围值的相应范围（当x + 1不在集合中时，x结束范围）。 这给你所有相关的连续范围。
• 返回距离其最远的连续范围。

C＃代码：

 static Tuple<int, int> FindLargestContiguousRange(this IEnumerable<int> items) { var itemSet = new HashSet<int>(items); // find contiguous ranges by identifying their starts and scanning for ends var ranges = from item in itemSet // is the item at the start of a contiguous range? where !itemSet.Contains(item-1) // find the end by scanning upward as long as we stay in the set let end = Enumerable.Range(item, itemSet.Count) .TakeWhile(itemSet.Contains) .Last() // represent the contiguous range as a tuple select Tuple.Create(item, end); // return the widest contiguous range that was found return ranges.MaxBy(e => e.Item2 - e.Item1); } 

注意：MaxBy来自MoreLinq

testing

小健康检查：

 new[] {3,6,4,1,8,5}.FindLargestContiguousRange().Dump(); // prints (3, 6) 

大的连续列表：

 var zeroToTenMillion = Enumerable.Range(0, (int)Math.Pow(10, 7)+1); zeroToTenMillion.FindLargestContiguousRange().Dump(); // prints (0, 10000000) after ~1 seconds 

大分散列表：

 var tenMillionEvens = Enumerable.Range(0, (int)Math.Pow(10, 7)).Select(e => e*2); var evensWithAFewOdds = tenMillionEvens.Concat(new[] {501, 503, 505}); evensWithAFewOdds.FindLargestContiguousRange().Dump(); // prints (500, 506) after ~3 seconds 

复杂

该algorithm需要O（N）时间和O（N）空间，其中N是列表中项目的数量，假设集合操作是恒定时间。

请注意，如果该集合是作为input提供的，而不是由algorithm构build，那么我们只需要O（1）空间。

（有些评论说这是二次的，我认为他们假设所有的项目，而不是在范围开始的项目，触发扫描，如果algorithm这样的话，那确实是二次的。

Answer 9

我想我会把它们sorting成连续的整数列表（假设每个数字只能出现一次）

拿第一个号码

如果数字1低于或高于现有列表中的数字1？

是：前/后现有的列表

否：从当前编号开始新build一个列表

如果有更多的数字，返回顶部

显示最长的列表

Answer 10

免责声明：由于解决scheme是基于哈希表，预计运行时间，而不是最坏的情况。

这个O（n）解决scheme取决于整数是唯一的。 如果它们不是唯一的，则使用O（1）插入和成员查找来创build一个哈希集合，并且只要跳过已经遇到的数字，就像您浏览列表一样。

1. 创build一个O（1）查找/插入hashmap，其中的值是范围的开始，键是适合这些范围的末尾的数字。 对于值v和密钥k，这意味着从v开始并以k-1结束的范围位于密钥k处。

2. 浏览数字列表。 对于每个数字n检查地图在关键字n处是否有值v。 这对应于从v开始的范围，这将允许n在结尾。 如果存在，将v移至键n + 1，并删除键n处的条目。 如果没有任何范围，请在键n + 1处插入n。

3. 由于数字是唯一的，所以这些范围中没有一个重叠，但可能有一些连续的。 运行地图的键/值对。 对于每个密钥k和值v，如果映射在密钥k1 = v处具有值v1，则意味着存在从v1到k-1的范围。 在v1处插入v1，并删除条目k1 / v1。

4. 通过地图的k / v条目查找大小为kv的最大范围[v，k-1]，并使用运行最大值。

举个例子：

 setup: l = [1,3,5,7,4,6,10] m = {} iteration: process 1 : m = {2->1} process 3 : m = {2->1, 4->3} process 5 : m = {2->1, 4->3, 6->5} process 7 : m = {2->1, 4->3, 6->5, 8->7} process 4 : m = {2->1, 5->3, 6->5, 8->7} process 6 : m = {2->1, 5->3, 7->5, 8->7} process 10 : m = {2->1, 5->3, 7->5, 8->7, 11->10} concatenation of contiguous ranges: initial: m = {2->1, 5->3, 7->5, 8->7, 11->10} first concatenation: m = {2->1, 7->3, 8->7, 11->10}, k=7, v=5, k1=5, v1=3 second concatenation: m = {2->1, 8->3, 11->10}, k=8, v=7, k1=7, v1=3 result: largest range : [3,7] of size 5