Подсчет пар из массива с абсолютной разницей не менее минимального элемента в паре

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

Дан массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы найти количество пар (arr[i], arr[j]) , таких, что абсолютная разница между двумя элементами не меньше минимального элемента в массиве. пара.

Примеры:

Input: arr[] = {1, 2, 2, 3}
Output: 3
Explanation:
Following are the pairs satisfying the given criteria:

  1. (arr[0], arr[1]): The absolute difference between the two is abs(1 – 2) = 1, which is at least the minimum of the two i.e., min(1. 2) = 1.
  2. (arr[0], arr[2]): The absolute difference between the two is abs(1 – 2) = 1, which is at least the minimum of the two i.e., min(1. 2) = 1.
  3. (arr[0], arr[3]): The absolute difference between the two is abs(1 – 2) = 1, which is at least the minimum of the two i.e., min(1. 2) = 1.

Therefore, the total count of such pairs is 3.

Input: arr[] = {2, 3, 6}
Output: 2

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

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

Эффективный подход. Описанный выше подход также можно оптимизировать, отсортировав заданный массив, а затем повторив два вложенных цикла так, чтобы первый цикл выполнялся до N , а второй цикл выполнялся от arr[i] до (i%arr[i]) с приращением j как j += arr[i] до N и считать те пары, которые удовлетворяют заданным условиям. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте переменную, скажем, count как 0 , которая хранит результирующее количество пар.
  • Переберите диапазон [0, N], используя переменную i , и выполните следующие шаги:
    • Перебрать диапазон [arr[i] – (i%arr[i]), N], используя переменную j с приращением j как j += arr[i] и если i меньше j и abs(arr[ i] – arr[j]) является как минимум минимумом из arr[i] и arr[j] , а затем увеличивает счетчик на 1 .
  • После выполнения вышеуказанных шагов выведите в качестве результата значение count .

Ниже приведена реализация вышеуказанного подхода:

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

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