我在一次采访中被问到这个问题。给定一个整数列表，我们如何找到所有成员都在给定列表中的最大区间？
例如，给定列表 1,3,5,7,4,6,10，那么答案将是 [3, 7]。因为它包含 3 到 7 之间的所有元素。
我试图回答，但我没有说服力。我采取的方法是首先对列表进行排序，然后检查它的最大间隔。但我被要求这样做O(n)。
问问题
8206 次
10 回答
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 的定义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。
于 2013-07-11T11:46:10.427 回答
9
如果不希望排序，可以使用哈希映射和不相交集数据结构的组合。
为列表中的每个元素创建一个节点并将其插入到带有键 = 元素值的哈希映射中。然后查询 value+1 和 value-1 的哈希映射。如果找到任何东西，将当前节点与相邻节点所属的集合组合。完成列表后，最大的集合对应于最大的间隔。
时间复杂度为 O(N * α(N))，其中 α(N) 是反阿克曼函数。
编辑：实际上不相交集对于这个简单的任务来说太强大了。Grigor Gevorgyan 的解决方案不使用它。所以它更简单，更高效。
于 2013-07-11T11:22:38.763 回答
5
您可以权衡空间以在线性时间内得到它。
- 扫描列表中的最小值和最大值，S 和 L。
- 使用足够大的布尔数组或位向量 A 来容纳 (L - S + 1) 个条目。
- 再次浏览列表，将 A 的适当元素设置为 true，当您看到它时。
- 现在，A 已排序。遍历 A 并找到最大的连续真值集。
第一步在您的列表中是线性的。最后一个与 A 的大小呈线性关系，如果您只有几个相距甚远的值，则相对于您的列表可能会很大。但是，由于您正在处理整数，因此 A 是有界的。
于 2013-07-11T12:17:29.567 回答
3
1个想法：好吧，我认为无论如何您都必须对列表进行排序，但是您不能使用合并或快速排序。但是如果你有记忆，你可以使用对整数进行计数排序的想法。
所以你可以创建 0 和 1 的数组，从 0 到最大 int 值，如果你有值，然后用它们填充它，然后找到最大连续数组
2个想法：创建值字典，找到最小值和最大值 - 所有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)并找到最长的连续子集
>>> 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) 字典解决方案的代码（我只是喜欢它的简单性！！！）
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
于 2013-07-11T11:09:24.593 回答
2
我使用HashSet. 由于contains和remove是 O(1) 操作，您可以简单地从一个随机集合项创建一个新区间并“扩展”它，直到您发现它的完整大小，然后从集合中删除项目。删除是关键，因为这是阻止您“重复”任何间隔的原因。
以这种方式考虑它可能会有所帮助 - 列表有 K 个间隔，其大小加起来为 N。那么，您的任务是发现这些间隔是什么，而不重复任何间隔或项目。这就是 HashSet 非常适合这项工作的原因 - 您可以在扩展间隔时有效地从集合中删除项目。然后，您需要做的就是跟踪最大的时间间隔。
- 将列表放入一个
HashSet - 当集合非空时：
- 从集合中随机删除一个项目
- 从该项目定义一个新的间隔
- 展开区间如下：
- 定义
i = interval.start-1 - 当集合包含
i时，从集合中移除i并减少两者i和interval.start - 在另一个方向重复步骤 2（从 向上扩展
interval.end）
- 定义
- 如果扩展后的区间大于之前的最大区间，则将新的区间记录为最大区间
- 返回最大间隔
这是Java中的解决方案：
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;
}
}
于 2013-07-11T16:37:04.320 回答
1
考虑到使用平均 O(1) 哈希表构建的字典，这将是线性的。
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 b-a > max_a_b:
max_a = a
max_b = b
max_a_b = b-a
print max_a, max_b
于 2013-07-11T12:22:58.353 回答
1
这是一个类似于 Grigor 的解决方案。两个主要区别是该解决方案存储顺序集的长度而不是其他索引，并且这消除了对最后一个哈希集迭代的需要。
遍历数组
通过查找和更新相邻的集合端点来构建哈希图：
Key - 数组值
值- 当键是顺序集的端点时，存储该集的长度。否则，请保持真实，以便您只考虑一次。
如果当前集合大小最长，则更新最长集合大小和最长集合开始。
为了清楚起见，这是一个 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;
于 2013-07-11T15:17:15.797 回答
0
诀窍是将项目视为一组而不是列表。这允许您识别位于连续范围的开头或结尾的项目，因为集合可让您检查是否存在 item-1 或 item+1。这样，您可以在线性时间和空间中解决问题。
伪代码：
- 枚举集合中的项目，查找位于范围开头的项目（当 x-1 不在集合中时，x 开始一个范围）。
- 对于作为范围开始的每个值，向上扫描直到找到相应的范围结束值（当 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
测试
小型健全性检查：
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
复杂
该算法需要 O(N) 时间和 O(N) 空间，其中 N 是列表中的项目数，假设集合操作是常数时间。
请注意，如果集合作为输入给出，而不是由算法构建，我们只需要 O(1) 空间。
（一些评论说这是二次时间。我认为他们假设所有项目，而不仅仅是范围开始处的项目，触发扫描。如果算法以这种方式工作，那确实是二次的。）
于 2013-07-11T14:19:15.990 回答
-1
我想我会把它们分类成连续整数列表（假设每个数字只能出现一次）
取第一个数字
如果数字 1 低于或高于现有列表中的数字？
是：前/后挂起现有列表
no : 创建一个从当前编号开始的新列表
如果有更多数字，返回顶部
显示最长的列表
于 2013-07-11T11:03:28.707 回答
-1
免责声明：由于该解决方案基于哈希表，因此运行时间是预期的，而不是最坏的情况。
这个 O(n) 解决方案取决于整数是唯一的。如果它们不是唯一的，则使用 O(1) 插入和成员查找创建一个哈希集，并在遍历列表时跳过已经遇到的数字。
制作一个 O(1) 查找/插入哈希图，其中值是范围的开头，键是适合这些范围末尾的数字。对于值 v 和键 k，这意味着从 v 开始并以 k-1 结束的范围位于键 k 处。
浏览数字列表。对于每个数字 n，检查映射是否在键 n 处具有值 v。这对应于从 v 开始的范围，最后允许 n 。如果有，将 v 移动到键 n+1 并删除键 n 处的条目。如果没有范围，则在键 n+1 处插入 n。
由于数字是唯一的，因此最后没有一个范围重叠，但可能有一些连续的范围。遍历映射的键/值对。对于每个键 k 和值 v，如果映射在键 k1 = v 处有一个值 v1，则意味着存在从 v1 到 k-1 的范围。在 k 处插入 v1，并删除条目 k1/v1。
遍历映射的 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
于 2013-07-11T11:50:36.513 回答