Medium

题目描述

给你一个整数 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 。

提示：

  • -10^15 <= num <= 10^15

解题思路

这道题需要根据数字的正负性分别处理：

正数的处理策略：

  • 我们希望得到最小值，所以要将数字按升序排列
  • 但不能有前导零，所以需要找到最小的非零数字放在首位
  • 剩余数字（包括所有0）按升序排在后面

负数的处理策略：

  • 负数的绝对值越大，数值越小
  • 所以要让绝对值尽可能大，将数字按降序排列
  • 由于负数不存在前导零问题，直接降序即可

实现步骤：

  1. 处理特殊情况：如果 num 为 0，直接返回 0
  2. 记录符号，取绝对值进行处理
  3. 将数字转换为字符串，提取各个数字字符
  4. 根据正负性进行排序：
    • 正数：升序排列，然后将第一个非零字符移到开头
    • 负数：降序排列
  5. 重新组合数字并恢复符号

时间复杂度主要由排序决定，为 O(d log d)，其中 d 是数字的位数。

代码实现

class Solution {
public:
    long long smallestNumber(long long num) {
        if (num == 0) return 0;
        
        bool isNegative = num < 0;
        string digits = to_string(abs(num));
        
        if (isNegative) {
            // 负数：降序排列使绝对值最大
            sort(digits.begin(), digits.end(), greater<char>());
        } else {
            // 正数：升序排列，但要避免前导零
            sort(digits.begin(), digits.end());
            
            // 找到第一个非零字符，移到开头
            for (int i = 0; i < digits.size(); i++) {
                if (digits[i] != '0') {
                    swap(digits[0], digits[i]);
                    break;
                }
            }
        }
        
        long long result = stoll(digits);
        return isNegative ? -result : result;
    }
};

class Solution:
    def smallestNumber(self, num: int) -> int:
        if num == 0:
            return 0
        
        is_negative = num < 0
        digits = list(str(abs(num)))
        
        if is_negative:
            # 负数：降序排列使绝对值最大
            digits.sort(reverse=True)
        else:
            # 正数：升序排列，但要避免前导零
            digits.sort()
            
            # 找到第一个非零字符，移到开头
            for i in range(len(digits)):
                if digits[i] != '0':
                    digits[0], digits[i] = digits[i], digits[0]
                    break
        
        result = int(''.join(digits))
        return -result if is_negative else result

public class Solution {
    public long SmallestNumber(long num) {
        if (num == 0) return 0;
        
        bool isNegative = num < 0;
        char[] digits = Math.Abs(num).ToString().ToCharArray();
        
        if (isNegative) {
            // 负数：降序排列使绝对值最大
            Array.Sort(digits, (a, b) => b.CompareTo(a));
        } else {
            // 正数：升序排列，但要避免前导零
            Array.Sort(digits);
            
            // 找到第一个非零字符，移到开头
            for (int i = 0; i < digits.Length; i++) {
                if (digits[i] != '0') {
                    (digits[0], digits[i]) = (digits[i], digits[0]);
                    break;
                }
            }
        }
        
        long result = long.Parse(new string(digits));
        return isNegative ? -result : result;
    }
}

var smallestNumber = function(num) {
    if (num === 0) return 0;
    
    const isNegative = num < 0;
    const digits = Math.abs(num).toString().split('').map(Number);
    
    if (isNegative) {
        digits.sort((a, b) => b - a);
        return -parseInt(digits.join(''));
    } else {
        digits.sort((a, b) => a - b);
        
        if (digits[0] === 0) {
            for (let i = 1; i < digits.length; i++) {
                if (digits[i] !== 0) {
                    [digits[0], digits[i]] = [digits[i], digits[0]];
                    break;
                }
            }
        }
        
        return parseInt(digits.join(''));
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间复杂度O(d log d)
空间复杂度O(d)

其中 d 是数字的位数。时间复杂度主要由排序操作决定，空间复杂度用于存储数字字符数组。

相关题目