Как решить задачу на взятие части массива без использования вложенных операторов if?

Question

Дан массив возрастающих чисел и два числа.

Задача — написать метод, который из данного массива достанет ту часть, которая лежит между заданными числами (включительно).

Пример ввода: {1,3,5,6,9,11,24}, 4, 10
Пример вывода: [5, 6, 9]

Требования:

Метод должен быть public static.
Сигнатура метода int[] getSubArrayBetween(int[] numbers, int start, int end).

Вопрос в том, как решить эту задачу без использования вложенных if?

public static int[] getSubArrayBetween(int[] numbers, int start, int end) {
    if (numbers.length > 0 || start < end) {
        int len = 0;
        int resultCounter = 0;
        for (int i = 0; i < (numbers.length); i++) {
            if (start <= numbers[i] && numbers[i] <= end) {
                len++;
            }
        }
        int[] result = new int[len];
        for (int i = 0; i < (numbers.length); i++) {
            if (start <= numbers[i] && numbers[i] <= end) {
                result[resultCounter] = numbers[i];
                resultCounter++;
            }
        }
        return result;
    } else {
        return new int[0];
    }
}

Answer 1

Ваш код почти работает правильно, но есть несколько мелких ошибок, которые нужно исправить условие if (numbers.length > 0 || start < end) некорректно. Надо использовать оператор И (&&), так как нам нужно убедиться, что массив не пуст и start < end.

public static int[] getSubArrayBetween(int[] numbers, int start, int end) {
    // Проверяем корректность входных данных
    if (numbers.length == 0 || start > end) {
        return new int[0];
    }

    // Считаем длину результирующего массива
    int length = 0;
    for (int number : numbers) {
        if (start <= number && number <= end) {
            length++;
        }
    }

    // Заполняем результирующий массив
    int[] result = new int[length];
    int resultCounter = 0;
    for (int number : numbers) {
        if (start <= number && number <= end) {
            result[resultCounter++] = number;
        }
    }

    return result;
}

Answer 2

Чтобы избавиться от вложенных if, следует сразу проверить входные данные и в зависимости от проверки вернуть пустой массив, как показал в более раннем ответе @thisSasha.

Затем можно определить индексы левого и правого края подмассива и воспользоваться стандартным методом Arrays.copyOfRange для копирования содержимого массива между двумя индексами (не включая последний).

Например, если использовать обычный линейный поиск левого и правого индексов, можно вообще обойтись без условных операторов if, так как тела операторов цикла for будут пустыми.

Пример с линейным поиском:

public static int[] getSubArrayBetween(int[] numbers, int start, int end) {
    int n = numbers.length;
    if (n == 0 || start > end || end < numbers[0] || start > numbers[n - 1]) {
        return new int[0];
    }

    int left = 0;
    for (int i = 0; i < n && numbers[left] < start; i++, left++);
    
    int right = n;
    for (int j = n; j-- > left && numbers[right - 1] > end; right--);

    return Arrays.copyOfRange(numbers, left, right);
}

Пример использования:

System.out.println(Arrays.toString(
    getSubArrayBetween(new int[]{1,3,3,3,5,6,9,11,24}, 4, 10)
));
// [5, 6, 9]

Если входной массив достаточно большой, лучше воспользоваться бинарным поиском (en.wiki, ru.wiki) для определения индексов левого и правого края подмассива:

public static int[] getSubArrayBetween(int[] numbers, int start, int end) {
    int n = numbers.length;
    if (n == 0 || start > end || end < numbers[0] || start > numbers[n - 1]) {
        return new int[0];
    }

    int left = start < numbers[0] ? 0 : leftmost(numbers, start);
    int right = end > numbers[n - 1] ? n : rightmost(numbers, left, end);

    return Arrays.copyOfRange(numbers, left, right);
}

private static int leftmost(int[] numbers, int value) {
    int left = 0, right = numbers.length;
    while (left < right) {
        int mid = (left + right) >>> 1;
        if (numbers[mid] < value) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

private static int rightmost(int[] numbers, int left, int value) {
    int right = numbers.length;
    while (left < right) {
        int mid = (left + right) >>> 1;
        if (numbers[mid] > value) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return right;
}

БЛОГ НА HUSL

Как решить задачу на взятие части массива без использования вложенных операторов if?

Ответы (2 шт):