面试难题:数组大小-n包含来自[i,i + n)的数字

Question

给定一个未排序的数字数组,编写一个函数,如果数组由连续数字组成,则返回true.

例子:

1. 如果array为{5,2,3,1,4},则该函数应返回true,因为该数组具有从1到5的连续数字.

2. 如果array为{83,78,80,81,79,82},则该函数应返回true,因为该数组具有从78到83的连续数字.

3. 如果数组是{34,23,52,12,3},那么函数应该返回false,因为元素不是连续的.

4. 如果数组是{7,6,5,5,3,4},则函数应返回false,因为5和5不连续.

我提出了以下算法:

1. 找到数组的最大值和最小值

2. max-min + 1应该是数组的大小

3. 检查重复

4. 检查两者之间的所有连续数字

我怎样才能实现第四条道路？(复杂性应该是O(n))

其他建议是最受欢迎的.

Answer 1

如果输入数组是A:

1. 找到A的最小值和最大值,如果数组的大小错误,则返回False.

2. 创建一个大小相同的新数组B,最初为全零

3. 对于每个索引i,设B [A [i] - min] = 1.

4. 检查B是否仍包含任何零.

每个步骤花费O(n)时间.