给定数字乘积的最小数字

Submission

运行时间: 32 ms

内存: 16.0 MB

class Solution:
    def smallestNumber(self, n: int) -> str:
        if n == 1: return "1"
        lis = []
        for i in range(9,1,-1):
            while n % i == 0:
                n //= i
                lis.append(i)
        return "".join(str(i) for i in lis[::-1]) if n == 1 else "-1"

Explain

该题解的思路是使用贪心算法的方法，寻找能够整除给定数字n的最小数字。从最大的单数位数字9开始，依次降到2，尝试用n除以这些数字，以检查能否整除。每当发现n可以被当前数字i整除时，就将i加入结果列表，并用n除以i更新n。这个过程一直持续到n不能被2到9之间的任何数字整除。最后，将结果列表逆序并连接成字符串形式，因为要返回最小的数字，较小的数字应该位于前面。如果最终n不等于1，说明n包含比9更大的质因数，这时应该返回'-1'。

时间复杂度: O(log n)

空间复杂度: O(log n)

class Solution:
    def smallestNumber(self, n: int) -> str:
        if n == 1: return "1"  # 如果n为1，直接返回'1'
        lis = []  # 初始化列表用于存储因数
        for i in range(9, 1, -1):  # 从9到2遍历每个可能的因数
            while n % i == 0:  # 当n可以被i整除时
                n //= i  # 更新n为n除以i
                lis.append(i)  # 将i加入列表
        # 如果最后n为1，说明n被完全分解，返回逆序连接的字符串；否则，返回'-1'
        return "".join(str(i) for i in lis[::-1]) if n == 1 else "-1"

Explore

选择从9开始向下至2遍历的原因是为了尽可能地使用较大的因数，这样可以减少因数的个数，从而在最后连接数字时得到较小的数字。例如，如果n可以被9整除，选择9作为因数比选择3三次更能减少数字长度，从而得到一个较小的结果。如果从2向上至9遍历，会导致结果中较小的数字更多，而这些较小的数字多次出现会使得最终组合的数字更大。因此，从9到2的遍历顺序可以帮助我们得到尽可能小的数字。

是的，当n最终不等于1且返回'-1'时，这意味着n包含大于9的质因数。例如，如果n是22，在试图用2到9之间的任何数字整除22时，最终n将变为11，因为22可以被2整除一次。由于11是一个质数且大于9，所以剩余的数11无法被2到9之间的任何数字再次整除。这种情况下，因为11大于9且没有被完全分解，所以算法返回'-1'。

将因数添加到列表并最终逆序连接得到最小的数字的策略是基于贪心算法的思想。由于我们从大到小添加因数，这样可以确保每步都是使用最大可能的因数，减少因数的数量。在完成所有可能的整除后，逆序连接是因为较小的因数在最终数字中应该位于更高位以形成更小的数。这种方法在n能被2至9的数字完全分解时适用，但如果n包含大于9的质因数，这种方法就不适用，因为这时无法将n完全分解为2至9之间的因数。

如果n是一个质数，比如11，算法将无法找到2至9之间的任何数字来整除n。在这种情况下，n在尝试被所有的因数整除后仍然保持不变，即为11。因此，算法在最后检查是否n=1时发现n仍然大于1，因此返回'-1'。这表明11不能被分解为2至9的任何组合的乘积，因此无法得到一个有效的结果。