2160. 拆分数位后四位数字的最小和
2160. 拆分数位后四位数字的最小和
题目
You are given a positive integer num
consisting of exactly four digits. Split num
into two new integers new1
and new2
by using the digits found in num
. Leading zeros are allowed in new1
and new2
, and all the digits found in num
must be used.
- For example, given
num = 2932
, you have the following digits: two2
's, one9
and one3
. Some of the possible pairs[new1, new2]
are[22, 93]
,[23, 92]
,[223, 9]
and[2, 329]
.
Return _theminimum possible sum of _new1
andnew2
.
Example 1:
Input: num = 2932
Output: 52
Explanation: Some possible pairs [new1, new2] are [29, 23], [223, 9], etc.
The minimum sum can be obtained by the pair [29, 23]: 29 + 23 = 52.
Example 2:
Input: num = 4009
Output: 13
Explanation: Some possible pairs [new1, new2] are [0, 49], [490, 0], etc.
The minimum sum can be obtained by the pair [4, 9]: 4 + 9 = 13.
Constraints:
1000 <= num <= 9999
题目大意
给你一个四位 正 整数 num
。请你使用 num
中的 数位 ,将 num
拆成两个新的整数 new1
和 new2
。new1
和 new2
中可以有 前导 0 ,且 num
中 所有 数位都必须使用。
- 比方说,给你
num = 2932
,你拥有的数位包括:两个2
,一个9
和一个3
。一些可能的[new1, new2]
数对为[22, 93]
,[23, 92]
,[223, 9]
和[2, 329]
。
请你返回可以得到的 new1
和 new2
的 最小 和。
示例 1:
输入: num = 2932
输出: 52
解释: 可行的 [new1, new2] 数对为 [29, 23] ,[223, 9] 等等。
最小和为数对 [29, 23] 的和:29 + 23 = 52 。
示例 2:
输入: num = 4009
输出: 13
解释: 可行的 [new1, new2] 数对为 [0, 49] ,[490, 0] 等等。
最小和为数对 [4, 9] 的和:4 + 9 = 13 。
提示:
1000 <= num <= 9999
解题思路
拆分数字:
- 首先将
num
进行拆分,提取出每一位数字并存入一个数组中。
- 首先将
排序:
- 对数组中的数字进行升序排序。这是因为为了得到最小的和,我们希望将较小的数字分别分配到两个新数中。
交替分配数字:
- 从排序后的数组中,交替地将数字分配给两个新数。这是为了平衡两个新数,使它们尽可能小。
计算和:
- 最后将两个新数相加,返回其和。
复杂度分析
时间复杂度:
O(1)
- 提取数字的每一位:
O(log(num))
,其中num
是输入的四位数(即最多为 4 位)。 - 排序:
O(d log d)
,其中d
是数字的位数(最多为 4,所以d
的值最大为 4,排序时间常数)。 - 最终计算和:
O(d)
,这部分操作是常数时间。 - 总的时间复杂度为
O(1)
,因为所有操作的复杂度都与num
的位数直接相关,而位数是常数。
- 提取数字的每一位:
空间复杂度:
O(1)
,空间主要用于存储数字数组digits
,其大小为 4(数字最多为 4 位)。
代码
/**
* @param {number} num
* @return {number}
*/
var minimumSum = function (num) {
let digits = [];
// 提取数字的每一位
while (num) {
digits.push(num % 10);
num = Math.floor(num / 10);
}
// 对数字进行升序排序
digits.sort((a, b) => a - b);
let new1 = 0,
new2 = 0;
// 交替地将数字分配给 new1 和 new2
for (let i = 0; i < digits.length; i++) {
if (i % 2 === 0) {
new1 = new1 * 10 + digits[i];
} else {
new2 = new2 * 10 + digits[i];
}
}
// 返回两个数字的和
return new1 + new2;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
258 | 各位相加 | [✓] | 数学 数论 模拟 | 🟢 | 🀄️ 🔗 |
2535 | 数组元素和与数字和的绝对差 | 数组 数学 | 🟢 | 🀄️ 🔗 | |
2544 | 交替数字和 | 数学 | 🟢 | 🀄️ 🔗 |