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

algorithm java

2022-09-03 16:19:05

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

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

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

编写一个函数：

类解决方案 { 公共 int solution（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 查找数组中的最低值和最高值，并从最低到最高循环访问所有可能的值，然后返回缺失值。

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

“空列表和单个元素”

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

“单元素”

“两个要素”

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

答案 1

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

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

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

空间复杂度为.O(1)

答案 2

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

事实上，在最后有关于如何计算数组中元素总和的解释，而不做任何循环。

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

def solution(A):

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

    return result - sum(A)