Количество пар таких, что A[i], i, A[j] и j расположены в порядке возрастания
Дан массив A[] из N целых чисел. Задача состоит в том, чтобы найти количество пар индексов (1 ≤ i, j ≤ N) в массиве, таких что A[i] < i < A[j] < j.
Примеры :
Input: N = 8, A[] = {1, 1, 2, 3, 8, 2, 1, 4}
Output: 3
Explanation: The pairs satisfying the given condition are {(2, 4), (2, 8), (3, 8)}.
For the pair (2, 4): A[2] = 1(1-based indexing), A[4] = 3 and 1 < 2 < 3 < 4.
For the pair (2, 8): A[2] = 1, A[8] = 4 and 1 < 2 < 4 < 8.
For the pair (3, 8): A[3] = 2, A[8] = 4 and 2 < 3 < 4 < 8.Input: N = 2, A[] = {1, 2}
Output: 0
Наивный подход. Основной способ решения проблемы — пройтись по массиву с помощью двух вложенных циклов и проверить условие для каждой возможной пары.
Временная сложность : O(N 2 )
Вспомогательное пространство : O(1)
Эффективный подход : проблема может быть решена с использованием жадного подхода и бинарного поиска.
Given Condition is A[i] < i < A[j] < j. Lets break it into three separate conditions:
- A[i] < i
- i < A[j]
- A[j] < j
The elements of array having A[i] ≥ i will not satisfy the 1st and 3rd condition and hence will not be the part of any pair satisfying the given condition. For rest of the elements (say valid elements) 1st and 3rd conditions are already satisfied. So, among the valid elements, simply count the number of pairs (i, j) satisfying the 2nd condition i.e. i < A[j].
Следуйте инструкциям, чтобы решить проблему:
- Инициализируйте переменную (скажем, ans ) с 0, чтобы сохранить общее количество пар и вектор (скажем, v ) для хранения позиций допустимых элементов.
- При переборе массива, если элемент больше или равен своей позиции, пропустите итерацию, так как этот элемент никогда не сможет сформировать пару, удовлетворяющую требуемым условиям.
- В противном случае просто добавьте к ответу количество позиций меньше текущего элемента (для удовлетворения 2-го условия i < A[j]), которое можно вычислить по нижней границе вектора v позиций.
- Кроме того, в конце каждой итерации вставьте позицию каждого допустимого элемента в вектор v.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N * log(N))
Вспомогательное пространство: O(N)