跳转至

2165. 重排数字的最小值

题目描述

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

解法

方法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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)
}

评论