Найдите максимальное число, образованное перестановкой цифр одинаковой четности

Учитывая число N, задача состоит в том, чтобы максимизировать это число, выполняя заданные условия:

• Нечетная цифра числа может быть заменена только любой нечетной цифрой, присутствующей в данном числе.
• Четная цифра числа может быть заменена только любой четной цифрой, присутствующей в данном числе.

Примеры:

Input: N = 234
Output: 432
Explanation: The 0th index is swapped with 2nd index.

Input: N = 6587
Output: 8765
Explanation: The 0th index is swapped with 2nd index.
The 1st index is swapped with 3rd index.

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

Следуйте шагам, указанным ниже, чтобы реализовать идею:

• Преобразуйте данное число N в строку s (это упростит обход каждой цифры числа)
• Итерировать строку от 0 до s.length()-1 :
  • Используйте переменные для хранения максимального значения справа от текущего индекса (скажем, maxi ) и его позиции (скажем, idx ).
  • Перебрать строку от j = i+1 до s.length()-1
    • Если и i -я, и j -я цифры имеют одинаковую четность , а j -я цифра больше, чем i -я, тогда обновите maxi и idx .
    • В противном случае продолжайте итерацию.
  • Наконец, поменяйте s[i] на s[idx]
• Возвращает целочисленное значение строки s .

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

Сложность времени: O(N ² ), где N — длина заданной строки.
Вспомогательное пространство: НА)

Эффективный подход: эта проблема может быть эффективно решена на основе следующей идеи:

Store all even digits in non-increasing order and do the same for odd digits. 
Now replace all stored even digits of given number in non-increasing order with even digits in it and do the same for odd digits.

Следуйте шагам, указанным ниже, чтобы реализовать идею.

• Преобразовать данное число N в строку s .
• Переберите s и сделайте следующее:
  • Сохраните все четные цифры в строке (скажем, evenDigit ) и все нечетные цифры в другой строке (скажем, oddDigit ).
  • Отсортируйте обе строки в порядке невозрастания.
• Переберите s и сделайте следующее:
  • Используйте два итератора (скажем, itr1 и itr2 ), чтобы указать на следующую четную или нечетную цифру, которую нужно выбрать.
  • Если цифра в s четная, замените ее цифрой в evenDigit[itr1] и увеличьте itr1.
  • Если цифра в s нечетная, то замените ее цифрой вodDigit[itr2] и увеличьте itr2.
• Наконец, преобразуйте строку s в целое число и верните ее.

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

Сложность времени: O(M * log M), где M — количество цифр в N.
Вспомогательное пространство: О(М)