Абсолютная разность всех попарно последовательных элементов в наборе

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

Пример:

Input: s = {8, 5, 4, 3, 15, 20}

Output: 1 1 3 7 5

Explanation:

The set is : 3 4 5 8 15 20
The difference between 4 and 3 is 1
The difference between 5 and 4 is 1
The difference between 8 and 5 is 3
The difference between 15 and 8 is 7
The difference between 20 and 15 is 5

Input: s = {5, 10, 15, 20}

Output: 5 5 5 

Explanation:
The set is : 5 10 15 20
The difference between 10 and 5 is 5
The difference between 15 and 10 is 5
The difference between 20 and 15 is 5

В статье Абсолютная разница всех попарно следующих друг за другом элементов в массиве рассматривается подход к поиску абсолютной разницы всех попарно следующих друг за другом элементов в массиве.

Подход: Эту проблему можно решить с помощью алгоритма двух указателей. Мы будем использовать итераторы как два указателя для итерации набора и проверки заданного условия. Выполните следующие шаги, чтобы понять решение вышеуказанной проблемы:

1. Объявите два итератора itr1 и itr2, и оба они указывают на начальный элемент набора.
2. Увеличить itr2, т.е. itr2++ в начале цикла.
3. Вычтите значения, указанные itr1 и itr2, т.е. *itr2 – *itr1 .
4. Увеличивайте itr1 в конце цикла, это означает *itr1++.
5. Если itr2 достигает конца набора, то прерываем цикл и выходим.

В C++ элементы набора сортируются, а дубликаты удаляются перед сохранением в памяти. Следовательно, в приведенной ниже программе C++ разница между попарно последовательными элементами вычисляется в отсортированном наборе, как объяснено в приведенных выше примерах.

Ниже приведена программная реализация C++ описанного выше подхода:

Выход:

1 1 3 7 5

Временная сложность: O(n)
Вспомогательное пространство: O(n)