Question

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

解法

方法一

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)

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;
  }
}

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;
  }
};

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)
}