Помогите более эффективно решить задачу по Java (алгоритмы)

Question

Решаю задачу по алгоритмам. Ближайшее число. Ввод и вывод данных производятся через стандартные потоки ввода-вывода. Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.

Входные данные В первой строке задается одно натуральное число N, не превосходящее 1000 – размер массива.

Во второй строке содержатся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).

В третьей строке вводится одно целое число x, не превосходящее по модулю 1000.

Выходные данные Вывести значение элемента массива, ближайшее к x. Если таких чисел несколько, выведите любое из них.

Решил двумя способами:

public class NearestNumber {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int N = scn.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }
        int x = scn.nextInt();
        int count = 0;
        for (int a = 0; a < 1000; a++) {
            for (int i = 0; i < arr.length; i++) {
                if (x - arr[i] == a) {
                    count = arr[i];
                    break;
                }
            }
            if (count > 0) {
                break;
            }
        }
        System.out.println(count);
    }
}

Второй способ:

public class NearestNumberV2 {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int N = scn.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }
        int x = scn.nextInt();
        int MinDiff = 1000;
        int MinDiffIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            int count = Math.abs(arr[i]-x);
            if (count <= MinDiff){
                MinDiff = count;
                MinDiffIndex = i;
            }
        }
        System.out.println(arr[MinDiffIndex]);
    }
}

Оба решения после тестов имеют статус "Частичное решение". Первый способ прошел 8 тестов, второй - 14. Как еще можно решить данную задачу? Спрашиваю не для сдачи зачета\экзамена, а для себя.

Answer 1

Задача решается подобно обычной задаче нахождения минимума/максимума.

В примере ниже возвращается null в случае пустого массива.

public static Integer nearest(int x, int ... arr) {
    Integer min = null;
    Integer nearest = null;
    for (int i = 0, n = arr.length; i < n; i++) {
        int diff = Math.abs(arr[i] - x);
        if (min == null || diff < min) {
            min = diff;
            nearest = arr[i];
            if (diff == 0) {
                break;
            }
        }
    }
    return nearest;
}

Answer 2

Ваше второе решение почти верное. Единственная существенная ошибка - неудачное начальное значение для MinDiff. В комментарии уже писали что оно мало и иногда это приводит к ошибке. Можно увеличить его до 2001, программа отработает на 100%.

Ещё лучше не полагаться на условие, если можно обойтись без него. Надо вычислить начальный MinDiff по первому элементу массива:

import java.util.Scanner;

public class NearestNumberV2 {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        final int n = s.nextInt();
        final int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = s.nextInt();
        }
        final int x = s.nextInt();

        int minDiff = Math.abs(arr[0] - x);
        int nearestV = arr[0];
        for (int v : arr) {
            int diff = Math.abs(v - x);
            if (diff < minDiff){
                minDiff = diff;
                nearestV = v;
            }
        }
        System.out.println(nearestV);
    }
}

БЛОГ НА HUSL

Помогите более эффективно решить задачу по Java (алгоритмы)

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