在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}不是问题中的排列。如果有人可以解释，我也许可以解决我的问题。现在，我确实对其进行了修改，使其可以在日食上运行，经过测试，但在Codility上，我仍然会在以下行中不断出错：有人知道为什么会这样吗？数组超出范围，但我在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;
}
}
最佳答案
此解决方案在codility中得分为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
和其他一些