CodeRun/src/main/java/hrTechInterview/HrTechInterview02.java - develop - javapractice/JavaPractice

CodeRun/src/main/java/hrTechInterview/HrTechInterview02.java
173 строки8 KB
Кузьма W600DEV Даждъбогин
TSKJVPRCTC5-19 Ближайшее число. Через приоритетную очередь, где приоритет - близость к x
01 фев 2026, 16:17
01 фев 2026, 16:1756629d1
package hrTechInterview;

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.stream.Collectors;

/**
 * Программа находит в массиве элемент, самый близкий по величине к данному числу.
 */
public class HrTechInterview02 {
    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        // В первой строке задается одно натуральное число NN, не превосходящее 1000 — размер массива.
        int arraySize = Integer.parseInt(reader.readLine().trim());
        // Во второй строке содержатся NN чисел — элементы массива, целые числа, не превосходящие по модулю 1000.
//        TreeSet<Integer> treeSet = Arrays.stream(reader.readLine().trim().split(" "))
//                .map(Integer::parseInt)
//                .collect(Collectors.toCollection(TreeSet::new));

        // В третьей строке вводится одно целое число xx, не превосходящее по модулю 1000.
        // int goalDigit = Integer.parseInt(reader.readLine().trim());

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

        // int result = getMinDiffWithDefaultEducation(reader);

        // writer.write(String.valueOf(result));
        int[] s = Arrays.stream(reader.readLine().trim().split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        int result = HrTechInterview02.findClosestSorted(s, Integer.parseInt(reader.readLine().trim()));
        writer.write(String.valueOf(result));

        writer.close();
        reader.close();
    }

    private static int getMinDiffWithDefaultEducation(BufferedReader reader) throws IOException {
        // В первой строке задается одно натуральное число NN, не превосходящее 1000 — размер массива.
        int arraySize = Integer.parseInt(reader.readLine().trim());
        // Во второй строке содержатся NN чисел — элементы массива, целые числа, не превосходящие по модулю 1000.
        ArrayList<Integer> integers = Arrays.stream(reader.readLine().trim().split(" "))
                .map(Integer::parseInt)
                .collect(Collectors.toCollection(ArrayList::new));
        // В третьей строке вводится одно целое число xx, не превосходящее по модулю 1000.
        int goalDigit = Integer.parseInt(reader.readLine().trim());

        // Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу.
        int newDiff;
        int lastMinDiff = Math.abs(integers.getFirst() - goalDigit);
        int result = integers.getFirst();

        for (int i = 1; i < integers.size(); i++) {
            newDiff = Math.abs(integers.get(i) - goalDigit);
            if (newDiff < lastMinDiff) {
                lastMinDiff = newDiff;
                result = integers.get(i);
            }
        }
        return result;
    }

    /**
     * Важно понять: Если элемент при бинарном поиске найден, то вернем его и завершим метод,
     * а если не будет найден то метод Arrays.binarySearch вернет позицию, где поиск был завершон,
     * т.е между двумя ближайшими соседями и позиция поиска будет знаком минус.
     * Это соглашение о возврате для бинарного поиска.
     * low указывает на позицию, где должен быть элемент (первую позицию, где значение ≥ key).
     * Формула -(low + 1) гарантирует:
     * Отрицательное число → сигнал, что элемент не найден.
     * Можно восстановить позицию вставки: insertionPoint = -result - 1
     * Примеры:
     * Если Arrays.binarySearch вернет -5, значит поиск завершен на позиции 4, и искомое значение можно вставить на позицию 4.
     * int[] arr = {10, 20, 30, 40, 50};
     * int index = binarySearch0(arr, 0, 5, 30); // → вернёт 2
     * int index2 = binarySearch0(arr, 0, 5, 25); // → вернёт -3
     * @param arr
     * @param x
     * @return
     */
    public static int findClosestSorted(int[] arr, int x) {
        // Сортируем массив для бинарного поиска
        Arrays.sort(arr);

        // Бинарный поиск позиции, где мог бы находиться x
        int pos = Arrays.binarySearch(arr, x);

        // Если элемент найден точно то задача решена
        if (pos >= 0) {
            return arr[pos];
        }

        // Если элемент не найден, метод binarySearch возвращает (-(insertion point) - 1)
        int insertionPoint = -pos - 1;

        // Определяем границы для поиска ближайшего x, который меньше всех элементов
        if (insertionPoint == 0) {
            return arr[0];
        }
        // Или Определяем границы для поиска ближайшего x, который меньше всех элементов
        if (insertionPoint == arr.length) {
            return arr[arr.length - 1];
        }

        // Сравниваем два соседних элемента
        int left = arr[insertionPoint - 1];
        int right = arr[insertionPoint];
        int diffLeft = Math.abs(left - x);
        int diffRight = Math.abs(right - x);

        if (diffLeft < diffRight) {
            return left;
        } else if (diffRight < diffLeft) {
            return right;
        } else {
            // Если разницы равны, возвращаем меньший элемент
            return Math.min(left, right);
        }
    }

    /**
     * Компактная версия с обработкой всех случаев
     *
     * @param arr
     * @param x
     * @return
     */
    public static int findClosest(int[] arr, int x) {
        int closest = arr[0];
        int minDiff = Math.abs(arr[0] - x);

        for (int i = 1; i < arr.length; i++) {
            int diff = Math.abs(arr[i] - x);
            if (diff < minDiff || (diff == minDiff && arr[i] < closest)) {
                minDiff = diff;
                closest = arr[i];
            }
        }
        return closest;
    }

    /**
     * Решение 5: С использованием приоритетной очереди (PriorityQueue)
     *
     * @param arr
     * @param x
     * @return
     */
    public static int findClosestWithPriorityQueue(int[] arr, int x) {
        // Создаем приоритетную очередь, где приоритет - близость к x
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
            int diffA = Math.abs(a - x);
            int diffB = Math.abs(b - x);
            if (diffA != diffB) {
                return diffA - diffB;
            }
            return a - b; // при равной разнице меньший элемент имеет приоритет
        });

        // Добавляем все элементы в очередь
        for (int num : arr) {
            pq.offer(num);
        }

        // Первый элемент в очереди - ближайший
        return pq.peek();
    }
}