java - 计数元素排列检查

Question

在 codility 排列检查问题中:

A non-empty zero-indexed array A consisting of N integers is given.
A permutation is a sequence containing each element from 1 to N once, and only once.
For example, array A such that:
    A[0] = 4
    A[1] = 1
    A[2] = 3
    A[3] = 2
is a permutation, but array A such that:
    A[0] = 4
    A[1] = 1
    A[2] = 3
is not a permutation.
The goal is to check whether array A is a permutation.
Write a function:
class Solution { public int solution(int[] A); }
that, given a zero-indexed array A, returns 1 if array A is a permutation and 0 if it is not.
For example, given array A such that:
    A[0] = 4
    A[1] = 1
    A[2] = 3
    A[3] = 2
the function should return 1.
Given array A such that:
    A[0] = 4
    A[1] = 1
    A[2] = 3
the function should return 0.
Assume that:
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [1..1,000,000,000].
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

这是我的解决方案，但我有一个错误。我觉得，在代码可以正常运行之前，我需要检查一个额外的条件。当使用这样的数组进行测试时: A[4,1,3} ，它返回 1 而不是 0 。为了让这段代码完美工作，我还需要测试什么？我错过了它，因为我不明白为什么 a[]{4,1,3} 不是排列，为什么 A[] {4,1,3,2} 是问题中的排列。如果有人能解释一下，我也许就能解决我的问题。现在，我确实修改了它，使其现在可以在我的 Eclipse 上工作，经过测试，但在 codility 上，我仍然不断收到有关该行的错误: counter[A[i]] += 1;有人知道为什么会这样吗？数组超出范围，但我在 Eclipse IDE 上没有收到该错误。
谢谢

    public class Solution {

    /**
     * @param args
     */

    public static int solution(int[] A) {
        // write your code in Java SE 7
        int[] counter = new int[(A[0] * A.length)];
        int max = -1;
        int OccurBefore = -1; // store some random number for a start

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

            if (A[i] > max) {
                max = A[i];
            } 
                if (A[i] == OccurBefore) {
                    return 0;
                }

                if(A[i] != OccurBefore) {
                    OccurBefore = A[i];
                    counter[A[i]] += 1;

                }

        }

        if(A.length<max){
            return 0;
        }

        return 1;
    }



}

Answer 1

该解决方案的可理解性得分为 100:

/**
* https://codility.com/demo/results/demoYEU94K-8FU/ 100
*/
public class PermCheck {
  public static final int NOT_PERMUTATION = 0;
  public static final int PERMUTATION = 1;
  // (4,1,3,2) = 1
  // (4,1,3) = 0
  // (1) = 1
  // () = 1
  // (2) = 0
  public int solution(int[] A) {
    // write your code in Java SE 8
    int[] mark = new int[A.length + 1];

    for (int i = 0; i < A.length; ++i) {
        int value = A[i];
        if(value >= mark.length) {
             return NOT_PERMUTATION;
        }
        if(mark[value] == 0) {
            mark[value]=1;
        } else {
            return NOT_PERMUTATION;
        }
    }

    return PERMUTATION;
  }
}

您还可以在这里查看: https://github.com/moxi/codility-lessons/blob/master/Codility/CountingElements/PermCheck.java和其他一些人一起。