LC.P2578[最小和分割]

方法一：排序+贪心

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int splitNum(int num) {
        char[] s = Integer.toString(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(nlogn)$
  • 空间复杂度：$O(n)$

方法二：计数+贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int splitNum(int num) {
        int[] cnt = new int[10];
        int n = 0;
        while (num > 0) {
            ++cnt[num % 10];
            num /= 10;
            ++n;
        }
        int[] ans = new int[2];
        for (int i = 0, j = 0; i < n; ++i) {
            while (cnt[j] == 0) ++j;
            --cnt[j];
            ans[i & 1] = ans[i & 1] * 10 + j;
        }
        return ans[0] + ans[1];
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(C)$，其中$C = 10$