2160. 拆分数位后四位数字的最小和

🟢   🔖  贪心 数学 排序  🔗 力扣 LeetCode

题目

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: two 2's, one 9 and one 3. 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

解题思路

1. 拆分数字：

   • 首先将 num 进行拆分，提取出每一位数字并存入一个数组中。

2. 排序：

   • 对数组中的数字进行升序排序。这是因为为了得到最小的和，我们希望将较小的数字分别分配到两个新数中。

3. 交替分配数字：

   • 从排序后的数组中，交替地将数字分配给两个新数。这是为了平衡两个新数，使它们尽可能小。

4. 计算和：

   • 最后将两个新数相加，返回其和。

复杂度分析

• 时间复杂度：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	交替数字和		数学	🟢	🀄️ 🔗