Easy

题目描述

给你一个正整数 num ，将它分割成两个非负整数 num1 和 num2 ，使得：

  • num1 和 num2 的连接是 num 的一个排列。
    • 换句话说，num1 和 num2 中所有数字的出现次数之和等于 num 中该数字的出现次数。
  • num1 和 num2 可以包含前导零。

返回 num1 和 num2 可能的最小和。

注意：

  • 保证 num 不含前导零。
  • num1 和 num2 中数字的出现顺序可能与 num 中数字的出现顺序不同。

示例 1：

输入：num = 4325
输出：59
解释：我们可以将 4325 分割成 num1 = 24 和 num2 = 35，和为 59。可以证明 59 是最小的可能和。

示例 2：

输入：num = 687
输出：75
解释：我们可以将 687 分割成 num1 = 68 和 num2 = 7，最优和为 75。

约束：

  • 10 <= num <= 10^9

解题思路

解题思路

这道题要求将一个数字的各位数字重新分配给两个数字，使得这两个数字的和最小。

核心思路：

  1. 排序策略：要使两个数字的和最小，应该让较小的数字尽可能出现在高位。因此先将所有数字按升序排列。

  2. 交替分配：将排序后的数字交替分配给两个数字。这样可以保证两个数字的位数尽可能接近，同时小的数字优先分配给第一个数字的高位。

  3. 贪心思想：为了最小化和，我们希望：

    • 两个数字的位数尽可能相近（避免一个数字特别大）
    • 每个数字的高位尽可能小

算法步骤：

  1. 提取数字的所有位数并排序
  2. 交替将数字分配给 num1 和 num2
  3. 计算两个数字的和

举例说明：

  • 对于 num = 4325，排序后得到 [2,3,4,5]
  • 交替分配：num1 = 24，num2 = 35
  • 结果：24 + 35 = 59

这种方法保证了最优解，因为我们总是让最小的数字占据最高位。

代码实现

class Solution {
public:
    int splitNum(int num) {
        vector<int> digits;
        
        // 提取所有数字
        while (num > 0) {
            digits.push_back(num % 10);
            num /= 10;
        }
        
        // 排序数字
        sort(digits.begin(), digits.end());
        
        int num1 = 0, num2 = 0;
        
        // 交替分配数字
        for (int i = 0; i < digits.size(); i++) {
            if (i % 2 == 0) {
                num1 = num1 * 10 + digits[i];
            } else {
                num2 = num2 * 10 + digits[i];
            }
        }
        
        return num1 + num2;
    }
};

class Solution:
    def splitNum(self, num: int) -> int:
        # 提取并排序所有数字
        digits = sorted(str(num))
        
        num1, num2 = 0, 0
        
        # 交替分配数字
        for i, digit in enumerate(digits):
            if i % 2 == 0:
                num1 = num1 * 10 + int(digit)
            else:
                num2 = num2 * 10 + int(digit)
        
        return num1 + num2

public class Solution {
    public int SplitNum(int num) {
        List<int> digits = new List<int>();
        
        // 提取所有数字
        while (num > 0) {
            digits.Add(num % 10);
            num /= 10;
        }
        
        // 排序数字
        digits.Sort();
        
        int num1 = 0, num2 = 0;
        
        // 交替分配数字
        for (int i = 0; i < digits.Count; i++) {
            if (i % 2 == 0) {
                num1 = num1 * 10 + digits[i];
            } else {
                num2 = num2 * 10 + digits[i];
            }
        }
        
        return num1 + num2;
    }
}

var splitNum = function(num) {
    const digits = num.toString().split('').sort();
    let num1 = '';
    let num2 = '';
    
    for (let i = 0; i < digits.length; i++) {
        if (i % 2 === 0) {
            num1 += digits[i];
        } else {
            num2 += digits[i];
        }
    }
    
    return parseInt(num1) + parseInt(num2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(d log d)d 是数字的位数，主要消耗在排序上
空间复杂度O(d)存储数字的各位需要 O(d) 的空间

相关题目