Реализуйте пользовательский компаратор для моего PriorityQueue

Question

Я пытаюсь решить следующую проблему кода leetcode:

Учитывая отсортированный массив, два целых числа k и x, найдите k ближайших элементов к x в массиве. Результат также должен быть отсортирован в порядке возрастания. Если есть ie, меньшие элементы всегда предпочтительнее.

Пример 1: Ввод: [1,2,3,4,5], k = 4, x = 3

Выход: [1,2,3,4]

Пример 2: Вход: [1,2,3,4,5], k = 4, x = -1

Выход : [1,2,3,4]

Мое неверное решение на данный момент следующее:

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(arr.length, (a,b) -> a == b ? a - b : Math.abs(a-x) - Math.abs(b-x));

       for(int i=0; i<arr.length; i++) {
           pq.add(arr[i]);

       }



        ArrayList ints = new ArrayList<>();

        for(int i=0;i<k;i++) {
            ints.add(pq.poll());


        }
        return ints;
    }
}

Проблема в компараторе, который я передаю конструктору. Идея состоит в том, что я хочу, чтобы мой компаратор сортировал целые числа относительно минимального расстояния между любым целым числом i и входными данными x, а затем опрашивал k элементов из очереди. Как я могу реализовать функцию сравнения, которая сортирует элементы таким образом?

Answer 1

Я бы использовал метод по умолчанию Integer.compare. По сути, вам нужно сначала проверить сравнение абсолютной разности, и, если оно равно ie, выполнить обычное сравнение.

static int compare(int x, int a, int b) {
    int comp = Integer.compare(Math.abs(a - x), Math.abs(b - x));
    if (comp == 0) {
        return Integer.compare(a, b);
    }
    return comp;
}

Это позволяет довольно чисто написать фактическую реализацию очереди приоритетов

static List<Integer> findClosestElements(int[] arr, int k, int x) {
    PriorityQueue<Integer> queue = new PriorityQueue<>(
        arr.length, (a,b) -> compare(x, a, b));
    Arrays.stream(arr).forEach(queue::add);
    return queue.stream().limit(k).sorted().collect(Collectors.toList());
}

Answer 2

Здесь проблема не в вашей приоритетной очереди, но нам нужны два результата с разными форматами заказа. Ваша очередь выдаст верхние элементы K, но это никогда не будет в порядке возрастания, поскольку она упорядочивает элемент относительно расстояния от «X», поэтому для данного X = 4 элементы 3 и 5 находятся на одном уровне, поэтому ваш результат будет иметь данные типа [4,3,5].

Лучше иметь отдельную сортировку для списка результатов.

do Collections.sort(ints); и возвращать результат.

Answer 3

В вашей реализации вы не проверяете сценарий, в котором расстояние двух целых чисел совпадает с X.
Следующая реализация компаратора даст правильный результат:

PriorityQueue<Integer> pq = new PriorityQueue<>(arr.length, 
                (a,b) -> {
                    int comp = Integer.compare(Math.abs(a - x), Math.abs(b - x));
                    if(comp==0) {return Integer.compare(a, b);}
                    return comp;
                });