Подсчитайте все различные пары с разностью, равной K | Набор 2

Опубликовано: 19 Сентября, 2022

Учитывая целочисленный массив arr[] и положительное целое число K, задача состоит в том, чтобы подсчитать все различные пары с различиями, равными K .

Примеры:

Input: arr[ ] = {1, 5, 3, 4, 2}, K = 3
Output: 2
Explanation: There are 2 distinct pairs with difference 3, the pairs are {1, 4} and {5, 2} 

Input: arr[] = {8, 12, 16, 4, 0, 20}, K = 4
Output: 5
Explanation: There are 5 unique pairs with difference 4. 
The pairs are {0, 4}, {4, 8}, {8, 12}, {12, 16} and {16, 20}

Наивный подход и подход, основанный на сортировке и бинарном поиске, упоминаются в наборе 1 этой статьи.

Подход: временная сложность этой задачи может быть уменьшена до линейной сложности в среднем случае с помощью хеширования с помощью неупорядоченных карт в соответствии со следующей идеей:

For forming such unique pairs, if traversed from the smallest element, an element (say x) will form such a pair with another element having value (x+K).
When the difference K = 0 then the elements having frequency more than 1 will be able to form pairs with itself.

Выполните шаги, указанные ниже, чтобы решить проблему:

  • Инициализируйте неупорядоченную карту и поместите все элементы массива в карту.
  • Если заданное значение K равно 0 :
    • Если частота текущего элемента x больше 1, увеличьте счетчик на 1.
    • В противном случае попробуйте то же самое для других элементов.
  • Если заданное значение K не равно 0:
    • Найдите x + K на карте и, если он найден, увеличьте количество на 1.
    • В противном случае попробуйте другие элементы.
  • Вернуть счет .

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

Временная сложность: O(N) [В среднем случае, поскольку средняя временная сложность неупорядоченной карты равна O(1)]
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ