Количество пар элементов массива со средним значением не менее K
Опубликовано: 19 Сентября, 2022
Дан массив A[] размера N , состоящий из N целых чисел, задача состоит в том, чтобы подсчитать количество пар, среднее значение которых больше или равно K.
Пример:
Input: N = 4, K = 3, A = {5, 1, 3, 4}
Output: 4
Explanation: (5, 1), (5, 3), (5, 4) and (3, 4) are the required pairs with average greater or equal to K = 3.Input: N = 3, K = 3, A = {1, 2, 3}
Output: 0
Explanation: No pairs exist with average greater or equal to K = 3.
Подход: Эту проблему можно решить с помощью бинарного поиска первого вхождения элемента в на основе следующего наблюдения:
- Just need to find 2*K – A[i] because average of two numbers X and Y is K ≤ (X+Y)/2. Now replace X with the current element that we are traversing i.e A[i] then equation becomes Y ≥ 2*K-A[i].
- So for any element A[i] in the array A[] total number of pairs formed are all the numbers in A[] that are greater than or equal to 2*K-A[i] i.e size of array ‘A’ -index of 2*K-A[i].
- So go as left as possible in A[] and for that find the first occurrence of 2*K-A[i]. If 2*K-A[i] is not found in A[] then return the index of next greater element of 2*K-A[i] because if average ≤ (X+Y)/2 for any two integers then also average ≤ (X+Z)/2 for all Z ≥ Y.
Выполните следующие шаги, чтобы решить эту проблему:
- Отсортируйте массив A[].
- Пройдите массив A[] .
- Найдите первое вхождение 2*kA[i] для каждого элемента А [я] в А.
- Если 2*kA[i] не существует, найдите первое вхождение элемента чуть больше 2*kA[i] в массиве A и сохраните его результат в переменной (скажем, ind ).
- Если инд не -1, затем добавьте в ответ N-ind .
- Вернуть окончательный ответ после завершения обхода.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O (N log N)
Вспомогательное пространство: O(N)