本文共 3467 字，大约阅读时间需要 11 分钟。

给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。

由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。

如果无法得到答案，请返回一个空字符串。

示例 1：

输入：digits = [8,1,9]输出："981"

示例 2：

输入：digits = [8,6,7,1,0]输出："8760"

示例 3：

输入：digits = [1]输出：""

示例 4：

输入：digits = [0,0,0,0,0,0]输出："0"

提示：

• 1 <= digits.length <= 10^4
• 0 <= digits[i] <= 9
• 返回的结果不应包含不必要的前导零。

解题思路

首先要知道一个定理：能被3整除的数，其各位数之和也能被3整除。

对于任意正整数b，其十进制表示为$a_n...a_1{a}_0$，即：

• $b={\sum }_{n-1}^N{a}_{n}10^n$

由于

• $10^{n}mod3=[9\ast 10^{n-1}+10^{n-1}]mod3=10^{n-1}mod3=...=10mod3=1$

因此，得证。

那么剩下的问题就和一模一样了。

遍历整个数组然后将数分成三个部分，%3==0、%3==1和%3==2。

然后整个数组的和sum_all模3等于0，那么将这些数从大到小排序后合成的数就是最大值了。

如果等于1，那么我们需要从%3==1的数（只有1、4、7）中选一个最小的数t1，然后再从%3==2（只有2、5、8）中选两个最小的数并计算和t2，比较t1和t2选择最小的，然后从数组中去掉这些数，最后将剩余的数从大到小排序。

如果等于2，那么我们需要从%3==2的数中选一个最小的数t1，然后再从%3==1中选两个最小的数并计算和t2，比较t1和t2选择最小的，然后从数组中去掉这些数，最后将剩余的数从大到小排序。

class Solution:    def largestMultipleOfThree(self, digits: List[int]) -> str:        digits.sort()        b1, b2, n = [], [], len(digits)        for i in range(n):            if digits[i] % 3 == 1 and len(b1) < 2: b1.append(i)            if digits[i] % 3 == 2 and len(b2) < 2: b2.append(i)                def get_result(x, y):            res = ""            for i in range(n - 1, -1, -1):                if i == x or i == y: continue                res += str(digits[i])                        if res and res[0] == "0": return "0"            return res                t = sum(digits) % 3        if t == 1:            if len(b1) >= 1:                return get_result(b1[0], -1)            return get_result(b2[0], b2[1])        elif t == 2:            if len(b2) >= 1:                return get_result(b2[0], -1)            return get_result(b1[0], b1[1])        return get_result(-1, -1)

评论区大佬提出了一种更加优秀的解法，就是通过基数排序可以实现O(n)的时间复杂。具体做法如下：

分别通过所有数字出现的次数cnt，那么%3==1的个数就等于b1 = cnt[1] + cnt[4] + cnt[7]，%3==2的个数就等于b2 = cnt[2] + cnt[5] + cnt[8]，注意此时b1和b2是数值而不是数组。接着可以推测出t=sum(digits)%3=(b1 + b2*2)%3。然后就是上述的算法判断t值大小，根据大小判断b1和b2减少多少。最后遍历整个cnt将结果输出，注意遍历的过程中除了考虑cnt中对应元素的变化还需考虑b1和b2的变化。

最后就是边界情况的考虑，也就是排除"0"开始的情况。

class Solution:    def largestMultipleOfThree(self, digits: List[int]) -> str:        cnt = [0] * 10        for i in digits: cnt[i] += 1                    b1, b2 = cnt[1] + cnt[4] + cnt[7], cnt[2] + cnt[5] + cnt[8]        t = (b1 + b2 * 2) % 3                if t == 1:            if b1 >= 1: b1 -= 1            else: b2 -= 2        elif t == 2:            if b2 >= 1: b2 -= 1            else: b1 -= 2                        res = ""        for i in range(9, -1, -1):            if i % 3 == 0:                while cnt[i]:                    res += str(i)                    cnt[i] -= 1            elif i % 3 == 1 and b1:                while cnt[i] and b1:                    res += str(i)                    cnt[i] -= 1                    b1 -= 1            else:                while cnt[i] and b2:                    res += str(i)                    cnt[i] -= 1                    b2 -= 1                if res and res[0] == "0": return "0"        return res

reference:

https://leetcode-cn.com/problems/largest-multiple-of-three/solution/fen-lei-tao-lun-by-zhu-zhen-yu-ajz34/

https://leetcode.com/problems/largest-multiple-of-three/discuss/517704/Java-Basic-Multiple-of-3-Clean-code-O(N)-~-2ms

我将该问题的其他语言版本添加到了我的

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/104498909 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！