最小和分割【LC2578】
给你一个正整数 num ，请你将它分割成两个非负整数 num1 和 num2 ，满足：
num1和 num2直接连起来，得到 num各数位的一个排列。
换句话说，num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。
num1 和 num2 可以包含前导 0 。
请你返回 num1 和 num2 可以得到的和的 最小 值。
注意：
num 保证没有前导 0 。
num1 和 num2 中数位顺序可以与 num 中数位顺序不同。
- 思路
- 局部最优：统计num中每个数字的出现次数，从0开始逐位构造，使两个数字的最高位最小
- 全局最优：使num1和num2的和最小
- 实现
class Solution { public int splitNum(int num) { // 贪心构造：高位一定是较小值 int[] count = new int[10]; while(num > 0){ count[num % 10]++; num /= 10; } int num1 = 0, num2 = 0; int index = 0, i = 0; while (i < 10){ if (count[i] == 0){ i++; }else if ((index & 1) == 0){ num1 = num1 * 10 + i; count[i]--; index++; }else{ num2 = num2 * 10 + i; count[i]--; index++; } } return num1 + num2; } }
复杂度
时间复杂度：O ( log n u m )
空间复杂度：O ( C )
