Максимум минус минимум в массиве

Я пытаюсь найти диапазон(max — min) массива с помощью рекурсии.
Так как, может быть только одно возвращаемое значение, я немного запутался, как идти об этой проблеме.
То, что я сделал до сих пор, это найти максимум и минимум рекурсивно, а затем использовать эту функцию в диапазоне, чтобы найти диапазон. Мне было интересно, можно ли сделать все просто рекурсивно.

public static int max(int[] array, int N) {
    int maximum;

    if (N >= array.length) {
        maximum = Integer.MIN_VALUE;
    } else {
        maximum = max(array, N + 1);
        if (array[N] > maximum) {
            maximum = array[N];
        }
    }

    return maximum;
}

public static int min(int[] array, int N) {
    int minimum;

    if (N >= array.length) {
        minimum = Integer.MAX_VALUE;
    } else {
        minimum = min(array, N + 1);
        if (array[N] < minimum) {
            minimum = array[N];
        }
    }

    return minimum;
}   

public static int range(int [] array)
{
    int max1 = max(array , 0);
    System.out.println(max1);
    int min1 = min(array , 0);
    System.out.println(min1);
    int range = max1 - min1;

    return range;
}

5 ответов

  1. Например, можно вернуть массив (0 будет иметь min, а 1-max) таким образом, можно вернуть оба значения.

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

    findMinMax(array, (min, max) -> { System.out.println(min + " " + max);});
    
    private void findMinMax(int[] array, BiFunction<Integer, Integer, Void> callback) {
        //Do things
        callback.apply(min, max);
    }
    
  2. Ваш алгоритм кажется waaaay слишком сложным для того, что вы пытаетесь сделать.

    Неясно, является ли рекурсия обязательным требованием. Если нет, то как насчет этого?

    public int range (int[] array) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int elem : array) {
            if (elem < min) min = elem;
            if (elem > max) max = elem;
        }
        return (max - min);
    }
    

    На мобильном телефоне поэтому я не могу тестировать какой-либо код, но он должен работать.

    EDIT: Ok извините, перечитывая ваш вопрос я вижу, что вы просто хотите знать, как это сделать с помощью рекурсии . Возможно, вы хотели бы сделать это ясно в самом названии 😉

  3. Вы можете предоставить int[] с min (index 0) и max (index 1) в пределах метода и сделать все в том же методе.

    public class Test {
    
    @org.junit.Test
    public void test() {
    
        int[] array = new int[] { -5,2,4,6,-10,44};
        int[] minmax = new int[ 2 ];
        minmax( array, minmax, 0 );
    
        assertEquals( "[-10, 44]", Arrays.toString( minmax ) );
    }
    
    public static void minmax(int[] array, int[] minmax, int N) {
        if (N >= array.length) {
            return;
        } else {
            minmax(array, minmax, N + 1);
            if (array[N] < minmax[0]) {
                minmax[0] = array[N];
            } 
            if (array[N] > minmax[1]) {
                minmax[1] = array[N];
            } 
        }
    }   
    

    }

  4. Если рекурсия действительно является требованием, и вам просто нужен диапазон, то это должно сделать это:

    public static int range(int [] array, int index, int min, int max)
    {
        if (index == array.length) {
            if (index == 0)
                return 0;
            else
                return max - min;
        }
        else {
            int value = array[index];
            return range(array, index + 1, Math.min(value, min), Math.max(value, max));
        }
    }
    
    public static int range(int [] array)
    {
        return range(array, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
    }
    
  5. Эта проблема не имеет никакого улучшения от рекурсии, так как это итерационная проблема, которая вместо этого может привести к проблеме производительности из — за увеличения размера стека, в частности для больших массивов.
    В любом случае, более классическим примером в java 7 может быть следующее, Где вы можете использовать минимальный класс «пара» для хранения минимальных / максимальных значений

    public class MaxMinRecurse {
    
        void evalMaxMinInInterval(Couple maxmin, int pos, int[] values) {
            if (pos >= values.length)
                return;
            int x = values[pos];
            if (x < maxmin.min) {
                maxmin.min = x;
            } else if (x > maxmin.max) {
                maxmin.max = x;
            }
            evalMaxMinInInterval(maxmin, pos + 1, values);
        }
    
        public static void main(String[] args) {
            MaxMinRecurse mmr = new MaxMinRecurse();
            int[] values = { 1, 5, 3, 4, 7, 3, 4, 13 };
            Couple result = mmr.new Couple();
            mmr.evalMaxMinInInterval(result, 0, values);
            System.out.println("Max: " + result.max + ", Min:" + result.min);
        }
    
        class Couple {
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
        }
    
    }