跳至主要內容

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


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

🟢   🔖  贪心 数学 排序  🔗 力扣open in new window LeetCodeopen in new window

题目

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 拆成两个新的整数 new1new2new1new2 中可以有 前导 0 ,且 num所有 数位都必须使用。

  • 比方说,给你 num = 2932 ,你拥有的数位包括:两个 2 ,一个 9 和一个 3 。一些可能的 [new1, new2] 数对为 [22, 93][23, 92][223, 9][2, 329]

请你返回可以得到的 new1new2最小 和。

示例 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各位相加[✓]数学 数论 模拟🟢🀄️open in new window 🔗open in new window
2535数组元素和与数字和的绝对差数组 数学🟢🀄️open in new window 🔗open in new window
2544交替数字和数学🟢🀄️open in new window 🔗open in new window