解决 Codility 的 PermMissingElem 测试的正确方法是什么？ （爪哇）

Question

我从 Codility 的代码测试练习中遇到了以下问题：

给出了一个由 N 个不同整数组成的零索引数组 A。该数组包含 [1..(N + 1)] 范围内的整数，这意味着正好缺少一个元素。

您的目标是找到缺失的元素。

写一个函数：

类解决方案 { public int 解决方案（int[] A）； }

给定一个零索引数组 A，返回缺失元素的值。

例如，给定数组 A 使得：

A[0] = 2 A[1] = 3 A[2] = 1 A[3] = 5

该函数应返回 4，因为它是缺少的元素。

假使，假设：

N为[0..100,000]范围内的整数； A 的元素都是不同的；数组 A 的每个元素都是 [1..(N + 1)] 范围内的整数。

复杂：

预期的最坏情况时间复杂度为 O(N)；预期的最坏情况空间复杂度为 O(1)，超出输入存储（不>计算输入参数所需的存储）。

可以修改输入数组的元素。

---

我的方法是将给定的数组转换为 ArrayList，使用 ArrayList 查找数组中的最低值和最高值，并从最低到最高遍历所有可能的值，然后返回缺失值。

这解决了示例问题，但我的问题似乎是在给定数组的以下条件下我无法获得正确答案：

“空列表和单个元素”

“缺少第一个或最后一个元素”

“单一元素”

“两个要素”

我做错了什么，解决这个问题的正确方法是什么？

原文由 steelmonkey 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

这个问题有一个数学解，基于 从 1 到 n 的连续整数之和等于 n(n+1)/2 的事实。

使用这个公式，我们可以计算出 1 to N+1 的总和。然后用 O(N) 时间复杂度我们计算数组中所有元素的实际总和。

完整总计与实际总计之间的差值将产生缺失元素的值。

空间复杂度是 O(1) 。

原文由 PM 77-1 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这个问题是时间复杂性课程的一部分。

https://codility.com/media/train/1-TimeComplexity.pdf

事实上，最后有关于如何在不进行任何循环的情况下计算数组中元素总和的说明。

这是 Python3 中的最终解决方案：

 def solution(A):

    n = len(A)+1
    result = n * (n + 1)//2

    return result - sum(A)

原文由 RobyB 发布，翻译遵循 CC BY-SA 4.0 许可协议