java - Codility PermCheck 解决方案不适用于少数数据集

Question

尝试解决实践中的适应性类(class)并致力于 this .

我用 Java 编写了我的代码并在广泛的输入范围内测试了代码，但是代码在 extreme_min_max、single 和 double 测试结果中失败了。

给出的假设:

N 是 [1..100,000] 范围内的整数。
数组 A 的每个元素都是 [1..1,000,000,000] 范围内的整数。

我的代码解释:
1. 对给定的数组进行排序。
2. 遍历数组中的每个元素以找到每个连续对之间的差异。如果差值不是 1，则它不是一个 perm，因此返回 0。如果数组中只有一个元素，则返回 1。

谁能帮我找出代码中的错误？

我的代码:

public int solution(int[] A)
{
    if(A.length == 1)
        return 1;

    Arrays.sort(A);
    for (int i = 0; i < A.length-1; i++)
    {
        long diff = Math.abs(A[i] - A[i+1]);
        if(diff!=1)
            return 0;
    }
    return 1;
}

Answer 1

这是一个简单且更好的实现，它以 O(N) 时间复杂度和 O(N) 空间复杂度运行。

public int solution(int[] A)
{ 
    int size = A.length;
    int hashArray[] = new int[size+1];

    for (int i = 0; i < size; i++)
    {
        if(A[i]>size)
            return 0;
        else
            hashArray[A[i]]+=1;
    }
    for(int i=1;i<=size;i++)
    if(hashArray[i]!=1)
    return 0;

    return 1;
}