解决Codility的PermMissingElem测试的正确方法是什么？(JAVA)

Question

我从Codility的代码测试练习中得到以下问题:

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

你的目标是找到缺少的元素.

写一个函数:

class Solution {public 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查找数组中的最低和最高值,并从最低到最高迭代所有可能的值,然后返回缺失值.

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

"空列表和单个元素"

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

"单一元素"

"两个要素"

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

Answer 1

该问题具有数学解决方案,基于从1到n的连续整数n(n+1)/2之和等于的事实.

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

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

空间复杂性是O(1).

Answer 2

问题陈述明确指出该数组将由“N 个不同的整数”组成，因此 N 必须至少为 2。如果我们用英语书写，N=0 和 N=1 根本没有意义，例如“An array made of 0 个不同的整数...”。

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

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

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

Answer 3

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

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 4

我在 java 中的解决方案 100% 检测到的时间复杂度： O(N)

import java.util.*;

class Solution {
public int solution(int[] arr) {

    if(arr.length == 0) return 1;

    int sumArr = 0;


    for(int i=0; i < arr.length; i++){

        sumArr = sumArr + arr[i];

    }


    int sumN = 0;

     for(int i=1; i <= arr.length+1; i++){

        sumN = sumN + i;

    }


    if(sumArr == sumN)  return arr.length;


    return  sumN - sumArr;
}

}