1

Написать функцию, которая берет параметрами непустой массив A, состоящий из N целых чисел (отсортированных в неубывающем порядке) и целое число K, проверяет содержит ли A числа 1,2, ..., K (каждое число от 1 до K) по крайней мере однин раз, и не сожержит других чисел. Например, используя следующие значения:

int[] A = {1,1,2,3,3};
int K = 3;

функция должна возвратить true. А если задать

int[] A = {1, 1, 3};
int K = 2;

или

int[] A = {1, 1, 2, 3};
int K = 2;

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

Я пробовал написать следующую функцию, но она работает неправильно

public boolean function(int[] A, int K){
  int n = A.length;
  for (int i = 0; i < n-1; i++){
    if (A[i+1] >= A[i]+1)
      return true;
    if (A[0] != 1 && A[i] != K)
      return false;
    else
      return true;
  }
  return true;
}

В чем может быть ошибка? Большое спасибо всем если кто найдет ошибку в коде.

ЗЫ: забыл добавить что сложность должна быть не хуже O(n).

8
  • почему если следующее число больше предыдущего больше чем на один то возвращается true? Плюс судя по всему из цикла выполняется только первая итерация, так как в любом случае будет заход в ветку с каким-нибудь return
    – Grundy
    8 сен 2018 в 18:43
  • @Grundy Потому что оно больше предыдущего на порядок. Возможно надо использовать рекурсию, но сложность должна быть не больше O(n).
    – Roman C
    8 сен 2018 в 18:45
  • если больше на порядок, то как оно может входить в последовательность 1,2, ..., K?
    – Grundy
    8 сен 2018 в 18:46
  • @Grundy Здесь как раз разница равна 1.
    – Roman C
    8 сен 2018 в 18:48
  • A[i+1] >= A[i]+1 -> A[i+1] = 5 и A[i]=1 - условию удовлетворяют, но совсем не значит что входят в последовательность до 3
    – Grundy
    8 сен 2018 в 18:50

4 ответа 4

3

Поскольку массив отсортирован, достаточно сделать следующее:

1) Проверить, что первый элемент равен 1
2) Проверить, что последний элемент равен K
3) Пройти в цикле от второго до последнего элемента, проверяя, что разница с предыдущим не превышает 1

Таким образом, ваше решение было практически верным, ошибка вкралась только в условии внутри цикла и возврате true вместо false в случае нарушения порядка.

public boolean function(int[] A, int K){
  int n = A.length;
  if (A[0] != 1)
      return false;
  if (A[n-1] != K)
      return false;
  for (int i = 1; i < n; i++){
    if (A[i] - A[i-1] > 1)
      return false;
  }
  return true;
}
7
  • Спасибо, что помогли мне доделать это.
    – Roman C
    9 сен 2018 в 22:52
  • Вернёт true на ([1, 1, 2, 3], 3), что неверно 10 сен 2018 в 2:09
  • @Kir_Antipov Судя про примеру в вопросе, это как раз верно.
    – MBo
    10 сен 2018 в 2:21
  • @MBo, ой, простите меня, слепого) Я уже подзабыл точную формулировку вопроса хД 10 сен 2018 в 2:22
  • Но все равно. Вбейте тогда массив { 1, -1, 0, 1, 2, 3 } и ту же тройку. Я клонил к тому, что в Вашем алгоритме кроется ошибка, позволяющая числам быть меньше предыдущих, а это уж точно неправильно 10 сен 2018 в 2:25
2

Пришло вот такое решение в лоб:

private static boolean check(int[] array, int k) {
    if (k == 0 && array.length > 0)
        return false;

    if (array[array.length - 1] != k || array[0] != 1)
        return false;

    for (int number = 1; number <= k; number++)
        if (Arrays.binarySearch(array, number) < 0)
            return false;

    return true;
}

Асимптотичекая сложность O(n*log(n)) Уверен, что можно быстрее

UPDATE

Решение работающее за O(N)

private static boolean check(int[] array, int k) {
    if (k == 0 && array.length > 0)
        return false;

    if (array[array.length - 1] != k || array[0] != 1)
        return false;

    int index = 0;
    int number = 1;
    while (number <= k) {
        while (index < array.length && array[index] == number)
            index++;

        if (array.length == index)
            return true;

        if (array[index] == number + 1)
            number++;
        else
            return false;

    }

    return true;
}
2
  • Сложность должна быть надо не больше O(n)
    – Roman C
    9 сен 2018 в 22:55
  • я ошибся с оценкой, последний алгоритм работает за линейное время и от k не зависит
    – Artem
    10 сен 2018 в 9:47
1

Напишите ф-ю, которая будет генерировать массив от 1 до K (оно же макс).

void count(int *array, int max)
{
    for (int i = 0; i < max; ++i)
    {
        array[i] = i+1;
    }
}

, и дальше в теле будет проверять, входит ли i элемент массива в заданный массив A., если хотя бы раз не входит - false, если все ок - true.

2
  • зачем генерировать, если можно просто проверить <K?
    – Grundy
    8 сен 2018 в 18:50
  • и так что получается O(n*k), надо не больше O(n).
    – Roman C
    8 сен 2018 в 18:55
1

Фактически ваша задача является задачей о сравнении множеств:

public boolean function(int[] a, int k) {
    if (a.length < k) {
        return false;
    }
    Set<Integer> set = Arrays.stream(a).boxed().collect(Collectors.toSet());
    return set.size() == k && IntStream.range(1, k + 1).allMatch(set::contains);
}
3
  • Можете оценить сложность?
    – Roman C
    9 сен 2018 в 22:46
  • В данном случае создаются два экземпляра HashSet, основанных на HashMap. Сложность операций put(), get() и contains() для HashMap - O(1) в лучшем случае и O(n) в худшем, зависит от реализации hashCode(). Полагаю, что поскольку речь идёт о натуральных числах, то hashCode() будет иметь хорошее распределение и соответственно сложность операций put() и get() будет O(1). Таким образом я полагаю, что сложность данного решения будет O(a.length + 2 * k). Думаете, я не ошибаюсь? Тут наверное можно сделать оптимизацию. Если a.length < k можно сразу же возвращать false. 10 сен 2018 в 1:07
  • Изменил код. Теперь сложность в лучшем случае O(1), в худшем O(a.length + k) 10 сен 2018 в 1:21

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.