本文主要是介绍LeetCode 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 <= 10 9 ^9 9
我们应该尽量平均分配数字到num1和num2，目的是让一个数字的值对结果的贡献变得更小，比如4325，如果分成4和325，那么325中的3就可以放到另一个数里，这样3就从百位变成了十位。其次，对于一个数字，我们应尽量把小的数字放在高位，比如43和34，应该选34。因此我们可以用贪心法，将数字从小到大排列，然后遍历排列好的数字，第一个数字放到num1中，第二个数字放到num2中，交替进行：
class Solution {
public:int splitNum(int num) {vector<int> v(10);while (num) {int last = num % 10;++v[last];num /= 10;}int num1 = 0;int num2 = 0;bool toNum1 = true;for (int i = 0; i < v.size(); ) {if (!v[i]){++i;continue;}if (toNum1){num1 = num1 * 10 + i;}else{num2 = num2 * 10 + i;}--v[i];toNum1 = !toNum1;}return num1 + num2;}
};
如果num有n位数字，则此算法时间复杂度为O(n)，空间复杂度为O(1)。
这篇关于LeetCode 2578.最小和分割的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
