Найти все пары в массиве в отсортированном порядке с минимальной абсолютной разницей
Учитывая целочисленный массив arr[] размера N , задача состоит в том, чтобы найти все различные пары, имеющие минимальную абсолютную разницу , и вывести их в порядке возрастания .
Примеры :
Input: arr[] = {4, 2, 1, 3}
Output: {1, 2}, {2, 3}, {3, 4}
Explanation: The minimum absolute difference between pairs is 1.Input: arr[] = {1, 3, 8, 10, 15}
Output: {1, 3}, {8, 10}
Explanation: The minimum absolute difference between the pairs {1, 3}, {8, 10} is 2.
Подход : Идея состоит в том, чтобы рассмотреть абсолютную разницу соседних элементов отсортированного массива. Выполните следующие шаги, чтобы решить проблему:
- Отсортируйте данный массив arr[].
- Сравните все соседние пары в отсортированном массиве и найдите минимальную абсолютную разницу между всеми соседними парами.
- Наконец, выведите все соседние пары, разности которых равны минимальной абсолютной разнице.
Ниже приведена реализация приведенного выше кода:
Временная сложность : O(NlogN)
Вспомогательное пространство : O(N), так как было занято N дополнительного пространства.