添加元素以使范围内的所有元素都存在于数组中

给定一个包含 N 个元素的数组，找出数组中的最小值 (A) 和最大值 (B)。目标是确定需要添加到数组中的最小元素数量，以确保范围 [A, B] 中的所有数字都至少出现一次。

注意：在查看解决方案之前，尝试提出一种方法来找到相同问题的多种方法，这最终会提高你的编码技能

方法 1 (排序)

1. 首先按升序排列数组中的元素。
2. 遍历排序后的数组，检查 arr[i] 和 arr[i+1] 之间的差是否等于 1。如果不等于 1，则通过计算差值 count = arr[i+1] - arr[i] - 1 来更新计数器 (count)。
3. 最后，返回 count 变量的值。

此方法涉及对数组进行排序，然后计算连续元素之间的间隙，以确定需要添加多少数字来填充这些间隙。

Java 实现

输出

时间复杂度： O(n log n) // 用于排序

辅助空间： O(1)

方法 2

1. 首先创建一个哈希数据结构来跟踪数组中的元素。
2. 保留两个变量来存储数组中找到的最小和最大元素。
3. 遍历从最小元素到最大元素的数字范围。
4. 对于范围内的每个数字，检查它是否存在于哈希中。如果不存在，则增加计数器以跟踪计数。
5. 最后，返回计数器的值。

此方法涉及使用哈希来有效地确定指定范围内缺失数字的计数。

Java 实现

输出

时间复杂度

1. 此代码的时间复杂度对于这两个操作都是 O(N)
2. 从数组构建哈希集 (HashSet<Integer> set) 需要 O(N) 时间，因为它涉及遍历数组一次。
3. 第二个循环从 minm 迭代到 maxm，这是一个基于输入数据的常量大小范围。因此，此循环也需要 O(N) 时间。
4. 总体时间复杂度为 O(N)。

空间复杂度

1. 由于以下原因，此代码的空间复杂度也是 O(N)
2. HashSet<Integer> set 用于存储数组中的元素。在最坏的情况下，当所有元素都不同时，它可以存储所有 N 个元素。因此，哈希集的空间复杂度为 O(N)。
3. 附加变量 count、maxm 和 minm 占用常量空间，不依赖于输入大小。
4. 总体空间复杂度为 O(N)。

方法 3 (使用布尔数组)

1. 我们可以创建一个布尔数组并将其所有值初始化为“false”。
2. 接下来，我们遍历输入数组，对于落在范围 [A, B] 内的每个数字，我们将布尔数组中对应的元素设置为“true”。
3. 为了找到范围 [A, B] 中缺失数字的计数，我们计算布尔数组中“false”值的出现次数。此计数表示我们必须添加到输入数组中的元素数量，以确保范围 [A, B] 中的所有数字都至少出现一次。
4. 此方法依赖于使用布尔数组标记指定范围内数字的存在，然后计算剩余的“false”值以确定所需的添加。

Java 实现

输出

说明

1. 首先，我们找出输入数组中的最小值和最大值。这些值决定了我们感兴趣的数字范围。
2. 接下来，我们创建一个布尔数组来表示此范围。此数组中的每个元素对应于指定范围内的数字，我们将其初始化为“false”以表示它们都尚未存在。
3. 然后我们遍历输入数组，对于指定范围内的每个数字，我们通过将布尔数组中对应的元素更改为“true”来将其标记为“存在”。
4. 一旦我们标记了目标范围内数组中的所有数字，我们就会计算布尔数组中剩余的“false”元素。此计数表示我们必须添加到数组中的元素数量，以覆盖指定范围内的所有数字。
5. 最后，我们将此计数作为结果返回。

时间复杂度

1. 代码遍历输入数组一次以查找最小值和最大值，这需要 O(N) 时间，其中 N 是输入数组的长度。
2. 然后它再次遍历输入数组以标记指定范围内的数字并计算缺失的元素。这同样需要 O(N) 时间。
3. 总时间复杂度为 O(N)，其中 N 是输入数组的大小。

空间复杂度

1. 空间复杂度主要由布尔数组 isElementPresent 决定，其大小等于输入数组中从最小值到最大值的数字范围（即 maxElement - minElement + 1）。
2. 因此，空间复杂度为 O(R)，其中 R 是输入数组中数字的范围，在大多数情况下可能显著小于 N。
3. 代码中使用的其他变量和数据结构占用常量空间。