Easy

题目描述

给你一个由恰好四位数字组成的正整数 num。将 num 拆分成两个新的整数 new1 和 new2，要求使用 num 中的所有数字。new1 和 new2 中可以有前导零，并且 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. 位数分配：可以分成 1+3位、2+2位、3+1位三种情况。经过分析，2+2位的分配方式能产生最小和，因为这样可以最大化利用较小数字的权重。

  2. 贪心策略：排序后设四个数字为 a ≤ b ≤ c ≤ d，最优分配方式是：

    • 将最小的两个数字 a 和 b 作为十位数
    • 将较大的两个数字 c 和 d 作为个位数
    • 这样构成的两个数为：10a + c 和 10b + d

  3. 正确性证明：这种分配方式确保了较小的数字获得更高的权重（十位），而较大的数字只影响个位，从而最小化总和。

例如对于 2932：排序后为 [2,2,3,9]，构成 23 和 29，和为 52。

时间复杂度主要在于排序四个数字，实际上可以用计数排序优化到 O(1)，但由于只有四个数字，差异不大。

代码实现

class Solution {
public:
    int minimumSum(int num) {
        vector<int> digits;
        while (num > 0) {
            digits.push_back(num % 10);
            num /= 10;
        }
        
        sort(digits.begin(), digits.end());
        
        return (digits[0] + digits[1]) * 10 + digits[2] + digits[3];
    }
};

class Solution:
    def minimumSum(self, num: int) -> int:
        digits = sorted([int(d) for d in str(num)])
        return (digits[0] + digits[1]) * 10 + digits[2] + digits[3]

public class Solution {
    public int MinimumSum(int num) {
        var digits = num.ToString().Select(c => c - '0').OrderBy(x => x).ToArray();
        return (digits[0] + digits[1]) * 10 + digits[2] + digits[3];
    }
}

var minimumSum = function(num) {
    const digits = num.toString().split('').map(Number).sort((a, b) => a - b);
    return (digits[0] + digits[1]) * 10 + digits[2] + digits[3];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(1)只需要处理固定的4个数字，排序时间为常数
空间复杂度O(1)只使用固定大小的数组存储4个数字

相关题目