拆分数位后四位数字的最小和

难度: Easy

给你一个四位正整数 num 。请你使用 num 中的数位，将 num 拆成两个新的整数 new1 和 new2 。new1 和 new2 中可以有 前导 0 ，且 num 中所有数位都必须使用。

比方说，给你 num = 2932 ，你拥有的数位包括：两个 2 ，一个 9 和一个 3 。一些可能的 [new1, new2] 数对为 [22, 93]，[23, 92]，[223, 9] 和 [2, 329] 。

请你返回可以得到的 new1 和 new2 的最小和。

示例 1：

输入：num = 2932
输出：52
解释：可行的 [new1, new2] 数对为 [29, 23] ，[223, 9] 等等。
最小和为数对 [29, 23] 的和：29 + 23 = 52 。

示例 2：

输入：num = 4009
输出：13
解释：可行的 [new1, new2] 数对为 [0, 49] ，[490, 0] 等等。
最小和为数对 [4, 9] 的和：4 + 9 = 13 。

提示：

1000 <= num <= 9999

Submission

运行时间: 19 ms

内存: 16.0 MB

class Solution:
    def minimumSum(self, num: int) -> int:
        array = list(str(num))
        array.sort()
        n = len(array)
        new1, new2 = [array[i] for i in range(n) if i % 2 == 0], [array[i] for i in range(n) if i % 2 == 1]
        return int(''.join(new1)) + int(''.join(new2))

Explain

首先，将整数num转换为字符串并将其每个字符存入一个列表中。接着，对这个列表进行排序，这样可以确保较小的数字排在前面，有利于构成较小的新整数。为了得到两个可能的最小整数，采用交错取数的方式，即从排序后的列表中，依次选择索引为偶数的元素构成一个新整数（new1），索引为奇数的元素构成另一个新整数（new2）。最后，将这两个新整数从字符串转换为整数并求和。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def minimumSum(self, num: int) -> int:
        # 将数字转换为字符串后转为字符列表
        array = list(str(num))
        # 对字符列表进行排序
        array.sort()
        # 根据排序后的列表，交错选择索引为偶数和奇数的元素
        new1, new2 = [array[i] for i in range(4) if i % 2 == 0], [array[i] for i in range(4) if i % 2 == 1]
        # 将字符列表转换为字符串，再转换为整数，最后返回两个整数的和
        return int(''.join(new1)) + int(''.join(new2))

Explore

将数字转换为字符串并对字符进行排序是为了让数字的每一位都能按照从小到大的顺序排列。这样做的目的是为了确保在构造新的两个整数时，可以更容易地通过选择位置来最小化这两个整数的值。排序确保了数字的每一位都被最优地分配到两个新整数中，从而达到最小化它们和的目的。

采用交错取数的方式是为了均匀地分配排序后的数字字符到两个新整数中。这种方法通过将排序后的最小的数字和次小的数字分别放在不同的整数中，可以有效地减少两个整数的值。例如，排序后最小的数字分配给第一个整数，第二小的数字分给第二个整数，以此类推，从而使得两个整数的组合尽可能小，最终实现整体和的最小化。

对于所有数位相同的情况，例如'2222'，这种方法依然能得到相对最小的和。因为无论如何分配这些相同的数字，构成的两个新整数都将是相同的。例如，无论是'22'和'22'，还是任何其他的组合，得到的新整数和总会是相同的。因此，即使这种方法在数位完全相同的特殊情况下不能进一步最小化结果，它仍然能保证得到可能的最小和。

在这种方法中，没有特殊处理来避免前导0的问题，因为在将字符数组转换回整数时，前导0自然不会影响整数的值。例如，若一个新整数为'02'，在转换为整数时，它会自动变为2，从而不影响最终的和。因此，即使在数字字符被分配时形成了前导0，这些0在最终的数值计算中会被忽略，不会影响结果。