LeetCode 题解工作台
重排数字的最小值
给你一个整数 num 。 重排 num 中的各位数字，使其值 最小化 且不含 任何 前导零。 返回不含前导零且值最小的重排数字。 注意，重排各位数字后， num 的符号不会改变。 示例 1： 输入： num = 310 输出： 103 解释： 310 中各位数字的可行排列有：013、031、103、…
2
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数学·结合·排序
答案摘要
我们首先用一个数组 记录 中每个数字的出现次数。 如果 是负数，那么数字应该按照从大到小的顺序排列，因此我们从 到 遍历 ，将数字按照出现次数从大到小的顺序排列。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·结合·排序 题型思路
题目描述
给你一个整数 num 。重排 num 中的各位数字，使其值 最小化 且不含 任何 前导零。
返回不含前导零且值最小的重排数字。
注意，重排各位数字后，num 的符号不会改变。
示例 1：
输入：num = 310 输出：103 解释：310 中各位数字的可行排列有：013、031、103、130、301、310 。 不含任何前导零且值最小的重排数字是 103 。
示例 2：
输入：num = -7605 输出：-7650 解释：-7605 中各位数字的部分可行排列为：-7650、-6705、-5076、-0567。 不含任何前导零且值最小的重排数字是 -7650 。
提示：
-1015 <= num <= 1015
解题思路
方法一：计数
我们首先用一个数组 记录 中每个数字的出现次数。
如果 是负数，那么数字应该按照从大到小的顺序排列，因此我们从 到 遍历 ，将数字按照出现次数从大到小的顺序排列。
如果是正数，我们首先找到第一个非 的数字，将其放在第一位，然后按照从小到大的顺序排列剩余的数字。
时间复杂度 ，其中 为数字 的大小。空间复杂度 。
class Solution:
def smallestNumber(self, num: int) -> int:
neg = num < 0
num = abs(num)
cnt = [0] * 10
while num:
cnt[num % 10] += 1
num //= 10
ans = 0
if neg:
for i in reversed(range(10)):
for _ in range(cnt[i]):
ans *= 10
ans += i
return -ans
if cnt[0]:
for i in range(1, 10):
if cnt[i]:
ans = i
cnt[i] -= 1
break
for i in range(10):
for _ in range(cnt[i]):
ans *= 10
ans += i
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate handle edge cases like leading zeros and negative numbers effectively?
- question_mark
Does the candidate demonstrate an understanding of sorting algorithms?
- question_mark
Does the candidate efficiently minimize the number while maintaining the sign?
常见陷阱
外企场景- error
Forgetting to handle leading zeros for positive numbers.
- error
Incorrectly handling negative numbers by failing to sort digits in descending order.
- error
Not maintaining the sign of the number after rearranging the digits.
进阶变体
外企场景- arrow_right_alt
Handling extremely large numbers efficiently.
- arrow_right_alt
Modifying the solution to handle floating-point numbers with rearranged digits.
- arrow_right_alt
Optimizing the solution for numbers with many repeated digits.