难度: Easy
给你一个正整数 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运行时间: 22 ms
内存: 16.0 MB
class Solution:
def splitNum(self, num: int) -> int:
cnt=Counter(str(num))
a,b=0,0
for i in range(1,10):
while cnt[str(i)]>0:
if a<b:
a=10*a+i
else:
b=10*b+i
cnt[str(i)]-=1
return a+b
这个题解的基本思路是，首先统计数字num中各个数字的出现次数。然后，从1到9遍历这些数字，并根据它们的出现次数，将数字依次分配给两个数num1和num2，始终将数字添加到当前和较小的那个数。通过这种方法，我们试图均衡num1和num2的数值，从而使它们的总和尽可能小。这种贪心策略通过比较两者的当前值来决定将下一个数字添加到哪个数，从而尽量保持两者的平衡。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def splitNum(self, num: int) -> int:
# 使用Counter统计num中每个数字的出现次数
cnt = Counter(str(num))
a, b = 0, 0 # 初始化两个结果数字num1和num2
# 遍历数字1到9
for i in range(1, 10):
# 当某个数字还有剩余未被完全分配时继续分配
while cnt[str(i)] > 0:
# 分配到当前和较小的数，以尽量保持平衡
if a < b:
a = 10 * a + i
else:
b = 10 * b + i
# 每分配一次，该数字的计数减一
cnt[str(i)] -= 1
# 返回两个数的和
return a + b
这种贪心策略并不总是能保证最终和的最小值。贪心策略是基于当前情况做出最优决策的方法，但它并不总是能得到全局最优解。例如，对于数字1122，按照题解的方法，第一个数字1会分配给num1，第二个1会分配给num2，然后两个2也会按照当前的大小平衡分配。这将导致num1和num2为112和12，和为124。但是最优的分割应该是121和12，和为133。这个例子显示了贪心策略可能无法达到最小和的情况。
题解中从1到9的遍历顺序是为了避免在数字的最前面不合适地放置0，因为0放在数字的开头会使数字的数值降低或变为0，影响最终的和。例如，如果0放在num1或num2的开始，可能会导致一个数字本质上没有增加任何值。而将0放置在非首位可以确保0的加入不会影响数字的有效值。如果处理不当，如将0作为首位添加，确实会影响最终的结果，因为这会导致一个数值本身大大降低。
在Python中，`Counter`类是一个专门用于计数的容器，继承自字典。使用`Counter`可以直接统计各元素的出现次数，非常适合用于统计频率的场景。相比于数组，`Counter`提供了更多的灵活性和内置功能，如自动处理不存在的键的情况。相比于普通字典，`Counter`还提供了如`most_common`等有用的方法，可以简化代码并提高效率。因此，`Counter`在处理此类计数问题时通常是更优选的选择。
在题解的策略中，数字的分配是从1到9，因此在构建数字的过程中不会出现前导0的情况。每个数字的分配都是基于非零数字，所以不会产生前导0的问题。如果0出现在输入数字num中，它将被添加到已经至少由一个非零数字的num1或num2中，因此，0只会增加数的量级，而不会成为前导0。