Сталкиваетесь ли вы с трудностями при решении проблем кода, связанных с счетчиком инверсий? Тогда мой сегодняшний блог для вас! Продолжай читать :)
Во-первых, позвольте мне сделать краткое вступление. Счетчик инверсий для массива указывает - насколько далеко (или близко) массив от сортировки. Если массив уже отсортирован, то счетчик инверсий равен 0. Давайте рассмотрим пример массива, arr = {8, 4, 2, 1}. Данный массив имеет шесть инверсий:
(8,4), (4,2), (8,2), (8,1), (4,1), (2,1). Это означает, что два элемента образуют инверсию, если i ‹j и a [i]› a [j]. Итак, основной подход, о котором вы думаете, будет использовать сортировку слиянием, но хорошо то, что мы можем легко сделать это на C ++, используя структуры данных на основе политик (PBDS). PBDS обеспечивает программисту высокую производительность, семантическую безопасность и гибкость по сравнению со стандартными структурами данных библиотеки std C ++.
Он работает так же, как и наборы. У него есть две другие функции, которые улучшают его (что решит нашу проблему количества инверсий):
- find_by_order (k): возвращает итератор, указывающий на k-й по величине элемент (начиная с 0).
- order_of_key (k): возвращает количество элементов в наборе, которые строго меньше K. Это займет O (log (n)) временной сложности.
Итак, используя функцию find_by_order (k), переберите каждый элемент в массиве, а также вставьте его в стек. Это даст количество элементов строго меньше, чем K. Но мы хотим, чтобы количество элементов было больше, чем K, поэтому вычтите find_by_order (i) из текущего размера стека. Следовательно, вы получите счет инверсии.
Чтобы узнать больше о PBDS, обратитесь к this.
