Необходимо оптимизировать данное решение

Question

Условие задачи: Разработчики сервиса сбора данных решили уменьшить количество возможных вариантов ответов. Для этого выбрали n различных целых чисел — канонические варианты. Но в системе уже имеется m старых ответов. Для каждого их этих m чисел необходимо найти ближайший из n канонических вариантов, т.е. с минимальным модулем разности.

Формат ввода В первой строке записано целое число n ( 1 ≤ n ≤ 5 0 0 0 0 ). Во второй строке записаны n целых чисел a1 a2 … an — канонические ответы. В третьей строке записано одно целое число m ( 1 ≤ m ≤ 5 0 0 0 0 ). В j -й из следующих m строк записано одно целое число bj . Гарантируется, что все входные числа не превосходят 10e6 по абсолютной величине.

Формат вывода Для каждого значения bj найдите каноническое значение (ближайшее). Если оптимальных значений несколько, выведите любое из них.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {

    public static void main(String[] args) {

        try (BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in))) {

            int n = Integer.parseInt(bufferedReader.readLine());
            int[] nArray = new int[n];
            if (n < 1 || n > 50000) return;

            String s = bufferedReader.readLine();
            String[] sArray = s.split(" ");

            for (int i = 0; i < n; i++) {
                nArray[i] = Integer.parseInt(sArray[i]);
            }

            int m = Integer.parseInt(bufferedReader.readLine());
            int[] mArray = new int[m];
            if (m < 1 || m > 50000) return;
            for (int j = 0; j < m; j++) {
                int bj = Integer.parseInt(bufferedReader.readLine());
                mArray[j] = bj;
            }


            int[] rezult = new int[m];

            for (int i = 0; i < mArray.length; i++) {
                int min = Math.abs(mArray[0] - nArray[0]);
                for (int j = 0; j < nArray.length; j++) {
                    int abs = Math.abs(mArray[i] - nArray[j]);
                    if (abs < min) {
                        min = abs;
                        rezult[i] = nArray[j];
                    }
                }
            }

            for (int i = 0; i < rezult.length; i++) {
                System.out.println(rezult[i]);
            }

        } catch (IOException e) {
            e.printStackTrace();
        }

    }
}

Answer 1

Понять идею того, что делает этот код, достаточно сложно. Первое, что бросается в глаза - дублирование кода. Общие замечания таковы : 1)для консольного ввода проще использовать класс Scanner; 2)пользовательский ввод подразумевает потенциальные ошибки, разумеется, это не должно ломать программу, посему это нужно обрабатывать в блоке try-catch; 3)требовать от пользователя предварительно вводить количество цифр, которые будут введены им же на следующем шаге - глупо, вы и так узнаете их количество после ввода, этот код излишний; 4)в большенстве случаев легче использовать коллекции, чем массивы (хотя в данном конкретном случае можно и массивы), учитывая, что ArrayList инкапсулирует в себе массив, производительность не пострадает; 5)как я уже говорил, дублирование кода - главное зло, никогда этого не делайте.

для начала давайте попробуем так:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

    public class Main {

        public static void main(String[] args) {

            List<Integer> nArray = inputData();
            List<Integer> mArray = inputData();

            //здесь выполняйте проверку пользовательского ввода

            List<Integer> rezult = new ArrayList<>();

            for (Integer m : mArray) {
                int min = Math.abs(mArray.get(0)-nArray.get(0));
                for (Integer n : nArray) {
                    int abs = Math.abs(m-n);
                    if (abs < min) {
                        min = abs;
                        rezult.add(n);
                    }
                }
            }

            System.out.println(rezult);

        }

        private static List<Integer> inputData() {
            try {
                return Arrays.stream(new Scanner(System.in).nextLine().split(" "))
                        .map(i -> Integer.valueOf(i.trim()))
                        .collect(Collectors.toList());
            } catch (NumberFormatException e) {
                return new ArrayList<>(1);
            }
        }

    }

Answer 2

1) Отсортировать массив a[]

2) Для каждого значения b[i] найти бинарным поиском подходящий индекс k из сортированного массива a[]

3) Выбрать минимальную разность из b[i]-a[k], a[k+1] - b[i] и вывести соответствующее число a[k] или a[k+1]

Этот подход обеспечивает сложность O(nlogn+mlogn), что для размерности 50000 даёт обычно приемлемую скорость, в отличие от использованного квадратичного способа (O(n*m)).

БЛОГ НА HUSL

Необходимо оптимизировать данное решение

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