c - 面试谜题 : array size-n contains numbers from [i, i + n)

Question

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

例子:

1. 如果数组是 {5, 2, 3, 1, 4}，那么函数应该返回 true，因为数组有从 1 到 5 的连续数字。

2. 如果数组是 {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. 检查中间的所有连续数字

如何实现第4条路径？(复杂度应该是O(n))

欢迎提出其他建议。

Answer 1

如果输入数组是A:

1. 求 A 的最小值和最大值，如果数组大小错误则返回 False。

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

3. 对于每个索引 i，令 B[A[i] - min] = 1。

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

每一步都需要 O(n) 的时间。