2165. Smallest Value of the Rearranged Number

2165. Smallest Value of the Rearranged Number #

题目 #

You are given an integer num. Rearrange the digits of num such that its value is minimized and it does not contain any leading zeros.

Return the rearranged number with minimal value.

Note that the sign of the number does not change after rearranging the digits.

Example 1:

Input: num = 310
Output: 103
Explanation: The possible arrangements for the digits of 310 are 013, 031, 103, 130, 301, 310.
The arrangement with the smallest value that does not contain any leading zeros is 103.

Example 2:

Input: num = -7605
Output: -7650
Explanation: Some possible arrangements for the digits of -7605 are -7650, -6705, -5076, -0567.
The arrangement with the smallest value that does not contain any leading zeros is -7650.

Constraints:

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

题目大意 #

给你一个整数 num 。重排 num 中的各位数字,使其值 最小化 且不含 任何 前导零。

返回不含前导零且值最小的重排数字。注意,重排各位数字后,num 的符号不会改变。

解题思路 #

  • 先将每个数字出现次数统计出来。然后将数字大小从小到大排序。如果原数是正数,当出现有数字 0 的情况的时候,需先将第二小的数字排列到第一个,再把 0 排列完。再继续排列第二小,第三小。。。
  • 如果原数是负数。那么就逆序排列,即先排列最大的数字,然后次大的数字,直到排列最小的数字。因为数字越大,对应的这个数的负数就越小。

代码 #

package leetcode

import "sort"

func smallestNumber(num int64) int64 {
	pos := true
	if num < 0 {
		pos = false
		num *= -1
	}
	nums, m, res := []int{}, map[int]int{}, 0
	for num != 0 {
		tmp := int(num % 10)
		m[tmp]++
		num = num / 10
	}

	for k := range m {
		nums = append(nums, k)
	}
	if pos {
		sort.Ints(nums)
	} else {
		sort.Sort(sort.Reverse(sort.IntSlice(nums)))
	}

	if nums[0] == 0 && len(nums) > 1 {
		res += nums[1]
		m[nums[1]]--
	}

	for _, v := range nums {
		if res != 0 {
			for j := m[v]; j > 0; j-- {
				res = res * 10
				res += v
			}
		} else {
			res += v
			tmp := m[v] - 1
			for j := tmp; j > 0; j-- {
				res = res * 10
				res += v
			}
		}
	}
	if !pos {
		return -1 * int64(res)
	}
	return int64(res)
}

⬅️上一页

下一页➡️

Calendar May 20, 2022
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者