Максимальное число путем замены цифр между позициями с одинаковой четностью

Опубликовано: 27 Февраля, 2023

Для заданного положительного целого числа N задача состоит в том, чтобы найти максимально возможное значение N после любого количества перестановок между цифрами, которые находятся в позициях с одинаковой четностью.

Примеры :

Input: N = 12345
Output: 54321
Explanation: Swap 1 with 5 [both in odd positions],  
and 2 with 4 [both in even positions] to obtain 54321.

Input: N = 738946
Output: 897643

Подход :

The problem can be solved by storing odd indexed and even indexed digits in two maxHeaps, and creating new number that has both parity indexed digits sorted in descending order.

Для решения этой проблемы можно использовать следующие шаги:

  • Инициализируйте 2 maxHeaps, четных и нечетных .
  • Перебирать цифры числа и сохранять четные индексированные цифры в четной maxHeap и нечетные индексированные цифры в нечетной maxHeap.
  • Создайте новый номер, выталкивая значения из maxHeaps, теперь новый номер будет иметь как четные индексированные цифры, так и нечетные индексированные цифры в порядке убывания.
  • Верните это число, так как оно является максимальным.

Ниже приведена реализация описанного выше подхода.

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

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