本文最后更新于 363 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
给你一个正整数 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
解法一:排序+贪心
算法思路:
将 num
的每个数位上的数字提取出来,然后将其排序,将排序后的数组中的数字按从大到小的顺序交替分配给 num1
和 num2
,返回 num1
和 num2
的和即可。
代码实现:
class Solution {
public int splitNum(int num) {
List<Integer> nums = new ArrayList<>();
while(num > 0){
nums.add(num % 10);
num /= 10;
}
Collections.sort(nums);
int num1 = 0, num2 = 0;
for(int i = 0; i < nums.size(); i++){
if(i % 2 == 0){
num1 = num1 * 10 + nums.get(i);
}else{
num2 = num2 * 10 + nums.get(i);
}
}
return num1 + num2;
}
}
位运算优雅版:
class Solution {
public int splitNum(int num) {
char[] s = (num + "").toCharArray();
Arrays.sort(s);
int[] ans = new int[2];
for(int i = 0; i < s.length; i++){
ans[i & 1] = ans[i & 1] * 10 + s[i] -'0';
}
return ans[0] + ans[1];
}
}
复杂度分析:
时间复杂度: O(n * logn),其中 n 为 num 的位数。
空间复杂度: O(n),其中 n 为 num 的位数。