Задача: 1200. Minimum Absolute Difference
Сложность: easy

Дан массив различных целых чисел arr, найдите все пары элементов с минимальной абсолютной разницей между любыми двумя элементами.

Верните список пар в порядке возрастания (по отношению к парам), каждая пара [a, b] следует условиям:
a, b из arr
a < b
b - a равна минимальной абсолютной разнице между любыми двумя элементами в arr

Пример:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.

👨‍💻 Алгоритм:

1⃣Инициализация вспомогательного массива:
Найдите минимальный элемент minElement и максимальный элемент maxElement в массиве arr.
Инициализируйте вспомогательный массив line размером maxElement - minElement + 1 и установите смещение shift равным -minElement.
Пройдите по массиву arr и для каждого элемента value увеличьте значение в индексе value + shift на 1.

2⃣Поиск минимальной абсолютной разницы:
Пройдите по вспомогательному массиву line, начиная с индекса, соответствующего минимальному элементу.
Проверьте значения на каждом индексе curr:
- если line[curr] равно 0, пропустите этот индекс.
- если line[curr] равно 1, сравните абсолютную разницу текущей пары currPairDiff с минимальной найденной разницей minPairDiff.
- если currPairDiff больше minPairDiff, продолжайте.
- если currPairDiff равно minPairDiff, добавьте эту пару в список ответов.
- если currPairDiff меньше minPairDiff, очистите список ответов, добавьте эту пару и обновите minPairDiff.

3⃣Возврат результата:
После прохождения всех элементов массива line, список ответов будет содержать все пары с минимальной абсолютной разницей. Верните список ответов.

😎 Решение:

class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        int minElement = arr[0];
        int maxElement = arr[0];
        for (int num : arr) {
            minElement = Math.min(minElement, num);
            maxElement = Math.max(maxElement, num);
        }
        int shift = -minElement;
        int[] line = new int[maxElement - minElement + 1];
        List<List<Integer>> answer = new ArrayList();

        for (int num : arr) {
            line[num + shift] = 1;
        }
        
        int minPairDiff = maxElement - minElement;
        int prev = 0;
        
        for (int curr = 1; curr <= maxElement + shift; ++curr) {
            if (line[curr] == 0) {
                continue;
            }
            
            if (curr - prev == minPairDiff) {       
                answer.add(Arrays.asList(prev - shift, curr - shift));
            } else if (curr - prev < minPairDiff) {
                answer = new ArrayList();
                minPairDiff = curr - prev;
                answer.add(Arrays.asList(prev - shift, curr - shift));                
            } 

            prev = curr;
        }  
        
        return answer;
    }
}

Ставь 👍 и забирай 📚 Базу знаний