Проблемы моего примера тестового решения Codility
Вопрос был Напишите функцию:
class Solution { общественное решение int (int [] A); } что для заданного массива A из N целых чисел возвращается наименьшее положительное целое число (больше 0), которое не встречается в A.
Например, если A = [1, 3, 6, 4, 1, 2], функция должна вернуть 5.
Учитывая A = [1, 2, 3], функция должна вернуть 4.
Учитывая A = [−1, −3], функция должна возвращать 1. Предположим, что:
N — целое число в диапазоне [1..100 000]; каждый элемент массива A является целым числом в диапазоне [−1 000 000..1 000 000]. Сложность:
ожидаемая временная сложность в наихудшем случае равна O(N); ожидаемая сложность пространства в наихудшем случае составляет O (N) (не считая памяти, необходимой для входных аргументов).
public static int solution(int[] A)
{
int min = 1;
boolean negArray = true;
for(int i = 0; i < A.length; i++)
{
if (A[i] > 0)
{
negArray = false;
if (A[i] < min)
{
min = A[i];
}
}
}
int i = 1;
while(contains(A, min+i))
{
i++;
}
if (negArray || A.length <= 0)
return 1;
return min + i;
}
public static boolean contains(int[] A, int x)
{
for(int i = 0; i < A.length; i++)
{
if (A[i] == x)
return true;
}
return false;
}
Это было мое решение, и я получил 25% правильности. Я хотел бы знать, что я сделал неправильно.
Не знаком с Codility, но разве он не сообщает вам, какие тестовые случаи не удались?
@ jsheeran нет.
Ответы 2
Вы можете упростить задачу, признав, что вам просто нужно отслеживать целые числа, которые вы видели в заданном вами массиве. Вам также необходимо учитывать крайние случаи, когда массив пуст или полученное значение будет больше, чем максимально допустимое значение. Наконец, вам нужно обеспечить сложность O (n), вы не можете продолжать цикл для каждого значения, с которым вы сталкиваетесь. Вот где булев массив пригодится. Смотри ниже -
public static int solution(int[] A)
{
int min = 1;
int max = 100000;
boolean[] vals = new boolean[max+1];
if (A.length == 0)
return min;
//mark the vals array with the integers we have seen in the A[]
for(int i = 0; i < A.length; i++)
{
if (A[i] < max + 1)
vals[A[i]] = true;
}
//start at our min val and loop until we come across a value we have not seen in A[]
for (int i = 1; i < max; i++)
{
if (vals[i] && min == i)
min++;
else if (!vals[i])
break;
}
if (min > max)
return max;
return min;
}
Наихудшим случаем для зацикливания является A.length + max, что равно O(N)
Перед назначением A[i] >= 0 && A[i] <= max необходимо проверить наличие vals[A[i]] = true.
отличный звонок @jsheeran, совсем забыл проверить значение из A[]
Спасибо. Не знаю, почему бы им не создать еще одну категорию оценки эффективности.
@KiteThorn это всего лишь часть общего решения. важно, чтобы большой O был как можно меньше. Если вы считаете, что моего ответа было достаточно, пожалуйста, отметьте его как ответ, чтобы закрыть свой вопрос :)
Это мое 100% решение для javascript:
function solution(A) {
// write your code in JavaScript (Node.js 8.9.4)
A.sort((a, b) => a - b);
let smallestPositive = 1;
for (let i = 0; i < A.length; i++) {
const currentInteger = A[i];
if (currentInteger > 0 && currentInteger === smallestPositive) {
smallestPositive = smallestPositive + 1;
} else if (currentInteger > smallestPositive) {
return smallestPositive;
}
}
return smallestPositive;
}
Вы начинаете счетчик с 1 (так как это наименьшее положительное целое число)
Затем, если вы сортируете массив, вы можете просто пройти по нему, и после того, как вы найдете первое положительное число, вы сравните значения с этим счетчиком, который увеличивается, если текущее значение равно. В противном случае вы возвращаете счетчик.
Недавно я выполнил все задачи по кодилизации на javascript, все на 100%, и это может помочь кому-то, если вы застряли.
https://github.com/Buzunda/codility-уроки
проблема здесь в том, что ваше решение не O (N), а в лучшем случае O (NlogN) в зависимости от алгоритма сортировки для javascript
На самом деле в лучшем случае будет O(N) из-за Timsort v8.dev/blog/сортировка по массиву для всех, кто использует V8, но в худшем случае действительно O(NlogN). Но я думаю не случайно, что это получается на 100% на кодильности, из-за того, когда она появляется на уроках, и я думаю, что так проще. Но, конечно, ваш код будет быстрее.
Я ошибался, полагая, что в лучшем случае это O (NlogN), однако при измерении сложности решений для вашей сложности используется наихудший случай. Таким образом, в то время как лучший случай - O (N), худший случай - O (NlogN), и поэтому ваша общая сложность составляет O (NlogN). Если бы это зависело от меня, я бы не позволил вашему решению пройти как O (N) по этой причине. По моему мнению, вы настолько быстры, насколько ваш худший случай, когда дело доходит до сложности.
Я согласен на 100%. Я просто думаю, что, отправляясь на собеседования по проблемам кодирования, хорошо иметь менталитет и не пытаться быть экстравагантным без причины. Если бы я получил эту задачу на собеседовании, я бы сначала выбрал свое решение, а затем, когда / если бы интервьюер спросил меня, могу ли я сделать это за O (N), я бы подумал и изменился соответственно. Выполнение очевидного медленного решения, которое дает вам O(N*N), может уже дать вам оценку 50%, мое решение, вероятно, даст вам по крайней мере 80%, а иногда и 100%. Ваше решение, конечно, всегда на 100%, но не всегда так просто.
Между прочим, ваша проверка содержимого заставляет ваш алгоритм выполняться более чем за O (N) раз.