2578-最小和分割

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

• num1 和 num2 直接连起来，得到 num 各数位的一个排列。
  • 换句话说，num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。
• num1 和 num2 可以包含前导 0 。

请你返回 num1 和 num2 可以得到的和的 最小 值。

注意：

• num 保证没有前导 0 。
• 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 <= 109

思考：4325 怎么分？

如果分成 432 和 5，那么 4 显然放在 5 这边更优，所以要均匀分。

如果分成 32 和 45，那么 23 比 32 更好；进一步地，分成 24 和 35 更好，所以把小的排在高位更优，大的排在低位更优。

设 s 是 num 的字符串形式，这等价于把 s 排序后，按照奇偶下标分组。

附：视频讲解

[sol1-Python3]

class Solution:
    def splitNum(self, num: int) -> int:
        s = sorted(str(num))
        return int(''.join(s[::2])) + int(''.join(s[1::2]))

[sol1-Java]

class Solution {
    public int splitNum(int num) {
        var s = Integer.toString(num).toCharArray();
        Arrays.sort(s);
        var a = new int[2];
        for (int i = 0; i < s.length; i++)
            a[i % 2] = a[i % 2] * 10 + s[i] - '0'; // 按照奇偶下标分组
        return a[0] + a[1];
    }
}

[sol1-C++]

class Solution {
public:
    int splitNum(int num) {
        string s = to_string(num);
        sort(s.begin(), s.end());
        int a[2]{};
        for (int i = 0; i < s.length(); ++i)
            a[i % 2] = a[i % 2] * 10 + s[i] - '0'; // 按照奇偶下标分组
        return a[0] + a[1];
    }
};

[sol1-Go]

func splitNum(num int) int {
	s := []byte(strconv.Itoa(num))
	sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
	a := [2]int{}
	for i, c := range s {
		a[i%2] = a[i%2]*10 + int(c-'0') // 按照奇偶下标分组
	}
	return a[0] + a[1]
}

复杂度分析

• 时间复杂度：O(m\log m)，其中 m 为 num 转成字符串后的长度。
• 空间复杂度：O(m)。