Skip to content

Latest commit

 

History

History
130 lines (88 loc) · 5.98 KB

second_minimum_element.md

File metadata and controls

130 lines (88 loc) · 5.98 KB

Поиск второго по минимальности элемента в массиве

Условие

Дан массив целых чисел, требуется найти второй по минимальности элемент в массиве.

Примеры

[-1, 2, 5, 8]

Ответ: 2
[2, 4, 5, 0, 1]

Ответ: 1
[-2, -1, 1, 2]

Ответ: -1

Решение

При решении подобных задач обращайте внимание на краевые случаи! Например, пустой массив или массив состоящий из только одного элемента, либо массив из одних и тех же чисел.

Сортировка

Первая мысль: отсортировать массив по возрастанию, после чего взять второй элемент, он и будет искомым.

public static void secondMinSort(int[] arr) {
    if (arr.length <= 1) {
        System.out.println("Нет второго по минимальности элемента");
        return;
    }

    Arrays.sort(arr);

    System.out.println("Второй по минимальности: " + arr[1]);
}

Это решение НЕВЕРНОЕ.

В нем есть сразу несколько проблем:

  • Сортировка всего массива ради нахождения второго по минимальности - это лишние накладные расходы и затраты.

  • Массив может состоять из одних и тех же чисел, в таком случае минимального не будет.

    Например: [1, 1, 1, 1]

    В этом случае нам надо вводить дополнительные проверки, на то, что наш искомый второй по минимальности элемент вообще существует. А сортировку мы уже сделали!

  • Повторяющиеся элементы могут сместить второй по минимальности элемент.

    Например: [1, 1, 2, 1], что после сортировки даст [1, 1, 1, 2]

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

В таком случае наш алгоритм преобразуется уже в совсем неприятный код:

public static void secondMinSort(int[] arr) {
    if (arr.length <= 1) {
        System.out.println("Нет второго по минимальности элемента");
        return;
    }

    Arrays.sort(arr);

    for (int i = 1; i < arr.length; i++) {
        if (arr[0] != arr[i]) {
            System.out.println("Второй по минимальности: " + arr[i]);
            return;
        }
    }

    System.out.println("Нет второго по минимальности элемента");
}

Сортировка работает за O(N * log(N)), что следует из документации по Arrays.sort.

Время работы: зависит от алгоритма сортировки, но в нашем случае O(N * log(N))

Память: O(1)

Проход по массиву

Оптимальным же решением здесь я вижу проход по массиву как в стандартном поиске минимального элемента, однако с заведением еще одной переменной, в которой мы будем хранить тот самый, второй по минимальности элемент.

Предположим, что минимальный элемент массива - это и есть его первый элемент. Второй по минимальности мы инициализируем просто числом-заглушкой, для удобства возьмем сразу Integer.MAX_VALUE. Далее пройдемся по массиву и если будем находить элемент меньше, чем наш предполагаемый минимум, то присвоим его минимальному, а в переменную, хранящую второй по минимальности, присвоим наш бывший минимум. Если же наш предполагаемый минимум сохранился, то сравним текущий элемент с тем, что у нас в хранится в переменной, хранящей второй по минимальности, если наш сравниваемый меньше, то присвоим его как второй минимум. Важно не забыть, что в массиве могут быть повторяющиеся элементы и добавить проверку на это.

public static void secondMin(int[] arr) {
    if (arr.length <= 1) {
        System.out.println("Нет второго по минимальности элемента");
        return;
    }

    int min = arr[0];
    int secondMin = Integer.MAX_VALUE;

    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            secondMin = min;
            min = arr[i];
        } else if (secondMin > arr[i] && arr[i] != min) {
            secondMin = arr[i];
        }
    }

    if (secondMin == Integer.MAX_VALUE) {
        System.out.println("Нет второго по минимальности элемента");
        return;
    }

    System.out.println("Второй по минимальности: " + secondMin);
}

Время работы: O(N)

Память: O(1)