LeetCode 题解工作台
按奇偶性交换后的最大数字
给你一个正整数 num 。你可以交换 num 中 奇偶性 相同的任意两位数字（即，都是奇数或者偶数）。 返回交换 任意 次之后 num 的 最大 可能值 。 示例 1： 输入： num = 1234 输出： 3412 解释： 交换数字 3 和数字 1 ，结果得到 3214 。 交换数字 2 和数字 …
2
题型
5
代码语言
3
相关题
当前训练重点
简单 · 堆
答案摘要
我们可以用一个长度为 的数组 统计整数 中所有数字出现的次数，用一个下标数组 记录当前最大可用偶数和奇数，初始时 为 $[8, 9]$。 接下来，我们依次遍历整数 的每个数字，如果数字为奇数，则取 下标为 对应的数字，否则取下标为 对应的数字。如果该数字出现的次数为 ，则需要将数字减 ，继续判断，直到存在满足条件的数。然后，我们更新答案，以及数字出现的次数，继续遍历，直到遍历到整…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 堆 题型思路
题目描述
给你一个正整数 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
解题思路
方法一：计数
我们可以用一个长度为 的数组 统计整数 中所有数字出现的次数，用一个下标数组 记录当前最大可用偶数和奇数，初始时 为 。
接下来，我们依次遍历整数 的每个数字，如果数字为奇数，则取 下标为 对应的数字，否则取下标为 对应的数字。如果该数字出现的次数为 ，则需要将数字减 ，继续判断，直到存在满足条件的数。然后，我们更新答案，以及数字出现的次数，继续遍历，直到遍历到整数 。
时间复杂度 ，空间复杂度 。
class Solution:
def largestInteger(self, num: int) -> int:
nums = [int(c) for c in str(num)]
cnt = Counter(nums)
idx = [8, 9]
ans = 0
for x in nums:
while cnt[idx[x & 1]] == 0:
idx[x & 1] -= 2
ans = ans * 10 + idx[x & 1]
cnt[idx[x & 1]] -= 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n log n) due to sorting the parity groups, and space complexity is O(n) to store the separate digit lists. Heap-based reconstruction can maintain similar bounds but allows easy retrieval of largest available digits per parity. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate quickly separates digits by parity and explains why swaps are limited by parity.
- question_mark
They prioritize placing larger digits in higher positions to maximize value.
- question_mark
They recognize sorting plus heap structure as the key pattern to efficiently compute the solution.
常见陷阱
外企场景- error
Swapping digits without considering parity, which violates problem constraints.
- error
Reversing digits incorrectly or using ascending order instead of descending order, resulting in suboptimal number.
- error
Using in-place swaps without tracking positions, leading to misplacement of largest digits in the reconstruction step.
进阶变体
外企场景- arrow_right_alt
Allow only a fixed number of swaps instead of unlimited swaps.
- arrow_right_alt
Extend to negative numbers, requiring careful handling of sign during swaps.
- arrow_right_alt
Compute the k-th largest number achievable using parity swaps.