难度: Easy
给你一个正整数 num 。你可以交换 num 中 奇偶性 相同的任意两位数字（即，都是奇数或者偶数）。
返回交换 任意 次之后 num 的 最大 可能值。
示例 1：
输入：num = 1234 输出：3412 解释：交换数字 3 和数字 1 ，结果得到 3214 。 交换数字 2 和数字 4 ，结果得到 3412 。 注意，可能存在其他交换序列，但是可以证明 3412 是最大可能值。 注意，不能交换数字 4 和数字 1 ，因为它们奇偶性不同。
示例 2：
输入：num = 65875 输出：87655 解释：交换数字 8 和数字 6 ，结果得到 85675 。 交换数字 5 和数字 7 ，结果得到 87655 。 注意，可能存在其他交换序列，但是可以证明 87655 是最大可能值。
提示：
1 <= num <= 109运行时间: 25 ms
内存: 16.0 MB
class Solution:
def largestInteger(self, num: int) -> int:
# Convert the input number to a list of digits
digits = list(str(num))
# Separate the odd and even digits
odd_digits = [int(d) for d in digits if int(d) % 2 != 0]
even_digits = [int(d) for d in digits if int(d) % 2 == 0]
# Sort the odd and even digits in descending order
odd_digits.sort(reverse=True)
even_digits.sort(reverse=True)
# Create a result list to store the rearranged digits
result = []
# Iterate over the original digits and replace them with the largest possible digit
# of the same oddity (odd or even)
for d in digits:
digit = int(d)
if digit % 2 != 0:
# Replace the current odd digit with the largest odd digit
result.append(str(odd_digits.pop(0)))
else:
# Replace the current even digit with the largest even digit
result.append(str(even_digits.pop(0)))
# Join the result list into a string and convert it back to an integer
return int(''.join(result))
solution = Solution()
num = 1234
max_num = solution.largestInteger(num)
print(max_num) # Output: 3412
首先将整数转换为数字列表。随后，分别提取出奇数和偶数位的数字，并对它们进行降序排序。在构建最终结果时，遍历原始数字列表，根据每个数字的奇偶性，从排序后的奇数或偶数列表中取出当前最大值进行替换。这种方式确保了每个位置上的数字是可能的最大值，从而使得整个数字尽可能大。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def largestInteger(self, num: int) -> int:
# Convert the input number to a list of digits
digits = list(str(num))
# Separate the odd and even digits
odd_digits = [int(d) for d in digits if int(d) % 2 != 0]
even_digits = [int(d) for d in digits if int(d) % 2 == 0]
# Sort the odd and even digits in descending order
odd_digits.sort(reverse=True)
even_digits.sort(reverse=True)
# Create a result list to store the rearranged digits
result = []
# Iterate over the original digits and replace them with the largest possible digit
# of the same oddity (odd or even)
for d in digits:
digit = int(d)
if digit % 2 != 0:
# Replace the current odd digit with the largest odd digit
result.append(str(odd_digits.pop(0)))
else:
# Replace the current even digit with the largest even digit
result.append(str(even_digits.pop(0)))
# Join the result list into a string and convert it back to an integer
return int(''.join(result))
solution = Solution()
num = 1234
max_num = solution.largestInteger(num)
print(max_num) # Output: 3412
直接在整数上操作数字的位置和值相对复杂，因为整数本身是不可变的，无法直接更改其内部的单个数字。通过将整数转换为数字列表，我们可以轻松访问和修改各个位置的数字，从而更灵活地进行排序和重新组合。列表提供了一种直观的方式来处理和交换数字，这对于实现题目要求的数字重新排列至关重要。
对奇数和偶数位的数字进行排序的目的是为了确保在构造最终的整数时，每个位置都能放置可能的最大值。通过对奇数和偶数分别进行降序排序，可以确保每次替换操作都使用当前可用的最大奇数或偶数，从而最大化整个数字的值。这种方法保证了在保持数字原有奇偶性的前提下，每个位置都是该奇偶类别中可能的最大数字，从而构造出最大的整数。
使用列表来存储奇数和偶数位的数字是因为列表在这种场景下提供了简单直观的动态数组功能，特别是方便地添加元素和弹出元素。虽然可以考虑使用其他数据结构如堆（优先队列）来自动保持元素的排序状态，但对于本问题，列表足够高效，因为我们只需要进行一次排序和连续的弹出操作，这使得列表成为一个简单且有效的选择。
是的，算法确保了每次替换操作都使用当前最大可能的奇数或偶数。这是通过将奇数和偶数列表进行降序排序，并在替换时从对应的列表中顺序弹出最前面的元素实现的。由于排序是降序的，列表的首个元素始终是当前可用的最大值，这保证了每次替换都能使得数字尽可能大。