Подсчет инверсий в перестановке первых N натуральных чисел
Опубликовано: 22 Сентября, 2022
Дан массив arr[] размера N , обозначающий перестановку чисел от 1 до N, задача состоит в том, чтобы подсчитать количество инверсий в массиве.
Примечание. Два элемента массива a[i] и a[j] образуют инверсию, если a[i] > a[j] и i < j.
Примеры:
Input: arr[] = {2, 3, 1, 5, 4}
Output: 3
Explanation: Given array has 3 inversions: (2, 1), (3, 1), (5, 4).Input: arr[] = {3, 1, 2}
Output: 2
Explanation: Given array has 2 inversions: (3, 1), (3, 2).
Различные методы решения счетчика инверсии обсуждались в следующих статьях:
- Наивная и модифицированная сортировка слиянием
- Использование дерева AVL
- Использование БИТ
Подход: Эту проблему можно решить с помощью бинарного поиска. Выполните следующие шаги, чтобы решить проблему:
- Сохраните числа в диапазоне [1, N] в порядке возрастания в векторе V .
- Инициализируйте переменную как 0 , чтобы сохранить количество инверсий в массиве, arr[] .
- Итерация в диапазоне [0, N-1], используя переменную i
- Сохраните индекс появления arr[i]в векторе V в переменном индексе .
- Добавьте количество чисел, имеющих позиции меньше индекса , которые присутствуют в векторе, V , поскольку они меньше, чем текущий элемент, и, таким образом, образуют инверсии.
- Удалите элемент с индексом позиции из вектора V .
- Выведите значение ans в качестве результата.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O (N * log (N))
Вспомогательное пространство: O(N)