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

Question

我从Codibility的代码测试练习中发现了以下问题：

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

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

编写一个函数：

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

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

例如，给定一个数组：

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

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

假定：

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

复杂性：

预期最坏情况时间复杂度为O（N）；预计最坏情况下的空间复杂度为O（1），超出输入存储（不是

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

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

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

“空列表和单个元素”

"缺少第一个或最后一个元素"

“单一元素”

"两个要素"

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

Answer 1

问题陈述明确规定数组将由“N个不同的整数”组成，因此N必须至少为2。如果我们用英语写N=0和N=1，它们就毫无意义，例如“一个由0个不同整数组成的数组……”。

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

有了这些初始条件和规定的假设，“单一元素”、“空列表”等测试是完全不合适的。

正确的生产代码很可能必须测试无效条件，但这不是挑战的既定目标。

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)

Answer 3

这个问题有一个数学解决方案，其基础是从1到n的连续整数之和等于n（n1）/2。

使用这个公式，我们可以计算从1到n1的和。然后用时间复杂度计算数组中所有元素的实际总和。

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

空间复杂度是O（1）。