Java - помощь с пониманием кода кодообразования

Question

Для теста проверки безопасности PermCheck я закодировал одно решение (см. Ниже), но оно действительно реально разрешило пример, приведенный в тесте кодовости, потому что в массиве имеется только несколько значений и небольшие значения , Я также добавил код ниже, который набрал 100%, это код, который я нашел в Интернете. Этот код очень сильно отличается от моего, и я не мог понять, как он/она смог получить ответ. Может кто-то, пожалуйста, объясните код шаг за шагом и как это приведет к ответу, пожалуйста.

Codility Тест:

PermCheck

Проверить массив А является ли перестановка.

Дается непустой нуль-индексированный массив A, состоящий из N целых чисел.

Перестановка - это последовательность, содержащая каждый элемент от 1 до N один раз и только один раз.

Например, массив A таким образом, что:

A[0] = 4 
A[1] = 1 
A[2] = 3 
A[3] = 2 

перестановка, но массив A таким образом, что:

A[0] = 4 
A[1] = 1 
A[2] = 3 

не перестановка, так как значение 2 отсутствует.

Целью является проверка того, является ли массив A перестановкой.

Написать функцию:

class Solution { 
    public int solution(int[] A); 
} 

, что при нулевой индексированный массив A, returns 1 если массив A является перестановкой и 0, если это не так.

Например, если массив А, что:

A[0] = 4 
A[1] = 1 
A[2] = 3 
A[3] = 2 

функция должна вернуть 1.

Учитывая массив А, что:

A[0] = 4 
A[1] = 1 
A[2] = 3 

функция должна возвращать 0.

Предположим, что:

• N - целое число в диапазоне [1..100'000];
• Каждый элемент массива A является целым числом в диапазоне [1..1'000'000'000].

Сложность:

• Ожидаемая сложность в худшем случае время O (N)
• Ожидаемое наихудший пространство сложность O (N), за хранение входного сигнала (не считая хранения необходимых для входных аргументов).
• Элементы входных массивов могут быть изменены.

100% Score Решение (найдено из Интернета):

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 PermSolution(int[] A) { 
    // write your code in Java SE 8 
    int[] mark = new int[A.length + 1]; 
    int counter = 0; 

    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; 
      ++counter; 
     } else { 
      return NOT_PERMUTATION; 
     } 
    } 

    return counter == A.length ? PERMUTATION : NOT_PERMUTATION; 
} 

Мое решение:

public int PermSolution(int[] A) 
{ 
    int perm = 1; 

    Arrays.sort(A); 

    if (A[0] != 1) return 0; 

    for (int i = 0; i < A.length; i++) 
    { 
     if (A[i] + 1 == A[i + 1]) 
     { 
      return perm; 
     } 

     if (A[i] + 1 != A[i + 1]) 
     { 
      return 0; 
     } 
    } 

    return perm; 

} 

Answer 1

Использование Arrays.sort() является своего рода оригинальным, что это не так, как я бы сделал это, хотя.

Чтобы комментировать свой код, это, вероятно, не работает из-за этого: return perm;

Допустим, у вас есть этот массив, который не является перестановкой:

A[0] = 4 
A[1] = 1 
A[2] = 2 

Один вы выполняете Arrays.sort(A), вы» придется это:

A[0] = 1 
A[1] = 2 
A[2] = 4 

Теперь давайте выполним ваш код:

if (A[0] != 1) return 0; 

A[0] действительно равна 1 Далее, для i==0 мы имеем:

if (A[i] + 1 == A[i + 1]) 
    { 
     return perm; 
    } 

A[i] + 1 равно 2 и A[i+1] также равна 2 условие является true, вы выполняете return perm; и, таким образом, вы завершаете выполнение с помощью return 1.

На самом деле, до тех пор, как ваш массив содержит 1 и 2, эта функция будет всегда return 1

Для того, чтобы работать, вы должны проверить все массива перед фактически возвращает значение.

Это должно работать:

public int PermSolution(int[] A) 
{ 

int perm = 1; 
Arrays.sort(A); 

if (A[0] != 1) return 0; 

for (int i = 0; i < A.length; i++) 
{ 
     if (A[i] + 1 != A[i + 1]) 
    { 
     return 0; 
    } 
} 

return perm; 

} 

Чтобы оптимизировать его еще больше, это должно работать, а также:

public int PermSolution(int[] A) 
    { 

    Arrays.sort(A); 

    for (int i = 0; i < A.length; i++) 
    { 
      if (A[i] != i+1) 
     { 
      return 0; 
     } 
    } 

    return 1; 

    } 

Answer 2

Почему мы не избежать Arrays.sort (A), чтобы получить эффективность вычислений ниже:

public static int PermSolution(int[] A) 
{ 
    int len=A.length; 
    if(len==1) 
     return A[0]==1 ? 1 : 0; 

    BitSet set=new BitSet(len+2); 

    for (int i = 0; i < len; i++) 
    { 
     if(A[i]>len || set.get(A[i])) 
      return 0; 

     set.set(A[i]); 
    } 
    return set.nextClearBit(1)==(len+1) ? 1 : 0; 
}