Задача на поиск минимального числа в массиве

Question

Решаю задачу на алгоритмы. Ревизия Ввод и вывод данных производятся через стандартные потоки ввода-вывода. В связи с визитом Императора Палпатина было решено обновить состав дроидов в ангаре 32. Из-за кризиса было решено новых дроидов не закупать, но выкинуть пару старых. Как известно, Палпатин не переносит дроидов с маленькими серийными номерами, так что все, что требуется - найти среди них двух, у которых серийные номера наименьшие.

Входные данные Первая строка входного файла содержит целое число N – количество дроидов. (2 ≤ N ≤ 1000), вторая строка – N целых чисел, по модулю не превышающих 2*109 – номера дроидов

Выходные данные Выведите два числа: первым – последний по величине из номеров дроидов (такого следует утилизировать в первую очередь), а вторым – предпоследний.

Примеры входные данные 5 10 2 3 1 5 выходные данные 1 2

Решил 2-мя способами. Конечно, они отличаются только тем, что первый сохраняет значения, а второй сохраняет индексы. До лучшего решения не додумался. Система выдает "частичное решение". Наставьте на истинный путь, пожалуйста. Вариант 1

public class Revision {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int N = scn.nextInt();
        int[] droid = new int[N];
        for (int i = 0; i < droid.length; i++) {
            droid[i] = scn.nextInt();
        }
        int min = droid[0];
        int predMin = droid[0];
        for (int i = 1; i < droid.length; i++) {
            if (droid[i] < min){
                predMin = min;
                min = droid[i];
            }
        }
        System.out.println(min + " " + predMin);
    }
}

Вариант 2

public class RevisionV2 {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int N = scn.nextInt();
        int[] droid = new int[N];
        for (int i = 0; i < droid.length; i++) {
            droid[i] = scn.nextInt();
        }
        int indexMin = 0;
        int indexPreMin = 0;
        for (int i = 1; i < droid.length; i++) {
            if (droid[i] < droid[indexMin]){
                indexPreMin = indexMin;
                indexMin = i;
            }
        }
        System.out.println(droid[indexMin] + " " + droid[indexPreMin]);
    }
}

Answer 1

Решение частичное, так как не обновляется predMin должным образом, когда текущий элемент массива больше минимума min, но меньше, чем predMin.

Также имеет смысл сразу сравнить два первых элемента в массиве, так как его размер не меньше 2.

Вариант решения:

int min;
int predMin;
if (droid[0] < droid[1]) {
    min = droid[0];
    predMin = droid[1];
} else {
    min = droid[1];
    predMin = droid[0];
}
for (int i = 2; i < N; i++) {
    int curr = droid[i];
    if (curr < min) {
        predMin = min;
        min = curr;
    } else if (curr < predMin) {
        predMin = curr;
    }
}
System.out.println(min + " " + predMin);

Answer 2

Для начала, вам не надо хранить массив в памяти - считайте данные и сразу смотрите минимумы

public static void Foo1(){
    Scanner scn = new Scanner(System.in);
    int N = scn.nextInt();
    int min = scn.nextInt();
    int pred = scn.nextInt();

    if (pred < min) {
        int tmp = pred;
        pred = min;
        min = tmp;
    }

    for (int i = 2; i < N; i++) {
        int next =  scn.nextInt();
        if (next < min)
        {
            pred = min;
            min = next;
        }
        else if (next < pred) {
            pred = next;
        }
    }

    System.out.println("pred:" + pred + " min:" + min);
}

Ну и если вам хочется покороче решение и ещё для общего случая, то можно использовать очередь с приортиетами, например

public static void Foo2(){
    Scanner scn = new Scanner(System.in);
    int N = scn.nextInt();
    PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

    for (int i = 0; i < N; i++) {
        int next =  scn.nextInt();
        pq.add(next);
        if (pq.size() > 2) pq.remove();
    }

    System.out.println("pred:" + pq.remove() + " min:" + pq.remove());
}

БЛОГ НА HUSL

Задача на поиск минимального числа в массиве

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