README.md

comments	difficulty	edit_url	rating	source	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/2100-2199/2165.Smallest%20Value%20of%20the%20Rearranged%20Number/README.md	1361	第 279 场周赛 Q2	数学 排序

2165. 重排数字的最小值

English Version

题目描述

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

解法

方法一

Python3

class Solution:
    def smallestNumber(self, num: int) -> int:
        if num == 0:
            return 0
        cnt = [0] * 10
        neg = num < 0
        num = abs(num)
        while num:
            num, v = divmod(num, 10)
            cnt[v] += 1
        ans = ""
        if neg:
            for i in range(9, -1, -1):
                if cnt[i]:
                    ans += str(i) * cnt[i]
            return -int(ans)
        if cnt[0]:
            for i in range(1, 10):
                if cnt[i]:
                    ans += str(i)
                    cnt[i] -= 1
                    break
        for i in range(10):
            if cnt[i]:
                ans += str(i) * cnt[i]
        return int(ans)

Java

class Solution {
    public long smallestNumber(long num) {
        if (num == 0) {
            return 0;
        }
        int[] cnt = new int[10];
        boolean neg = num < 0;
        num = Math.abs(num);
        while (num != 0) {
            cnt[(int) (num % 10)]++;
            num /= 10;
        }
        long ans = 0;
        if (neg) {
            for (int i = 9; i >= 0; --i) {
                while (cnt[i]-- > 0) {
                    ans = ans * 10 + i;
                }
            }
            return -ans;
        }
        if (cnt[0] > 0) {
            for (int i = 1; i < 10; ++i) {
                if (cnt[i] > 0) {
                    ans = ans * 10 + i;
                    cnt[i]--;
                    break;
                }
            }
        }
        for (int i = 0; i < 10; ++i) {
            while (cnt[i]-- > 0) {
                ans = ans * 10 + i;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    long long smallestNumber(long long num) {
        if (num == 0) return 0;
        vector<int> cnt(10);
        bool neg = num < 0;
        num = abs(num);
        while (num) {
            cnt[num % 10]++;
            num /= 10;
        }
        long long ans = 0;
        if (neg) {
            for (int i = 9; i >= 0; --i)
                while (cnt[i]--) ans = ans * 10 + i;
            return -ans;
        }
        if (cnt[0]) {
            for (int i = 1; i < 10; ++i) {
                if (cnt[i]) {
                    ans = ans * 10 + i;
                    cnt[i]--;
                    break;
                }
            }
        }
        for (int i = 0; i < 10; ++i)
            while (cnt[i]--) ans = ans * 10 + i;
        return ans;
    }
};

Go

func smallestNumber(num int64) int64 {
	if num == 0 {
		return 0
	}
	cnt := make([]int, 10)
	neg := num < 0
	if neg {
		num = -num
	}
	for num != 0 {
		cnt[num%10]++
		num /= 10
	}
	ans := 0
	if neg {
		for i := 9; i >= 0; i-- {
			for j := 0; j < cnt[i]; j++ {
				ans = ans*10 + i
			}
		}
		return -int64(ans)
	}
	if cnt[0] > 0 {
		for i := 1; i < 10; i++ {
			if cnt[i] > 0 {
				ans = ans*10 + i
				cnt[i]--
				break
			}
		}
	}
	for i := 0; i < 10; i++ {
		for j := 0; j < cnt[i]; j++ {
			ans = ans*10 + i
		}
	}
	return int64(ans)
}