java 解法, 执行用时: 5 ms, 内存消耗: 42.9 MB, 提交时间: 2023-09-18 14:27:57

class Solution {
    public String largestMultipleOfThree(int[] digits) {
        int[] cnt = new int[10];
        int[] modulo = new int[3];
        int sum = 0;
        for (int d : digits) {
            ++cnt[d];
            ++modulo[d % 3];
            sum += d;
        }
        
        final int left;
        int rest;
        final int mod = sum % 3;
        if (mod == 0) {
            left = rest = 0;
        } else {
            if (modulo[mod] >= 1) {
                left = mod;
                rest = 1;
            } else {
                // left = ~mod & 0b11;
                left = 2 * mod % 3;
                rest = 2;
            }
        }
        
        StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < 10; ++i) {
            char ch = (char) (i + '0');
            for (int j = 0; j < cnt[i]; ++j) {
                if (rest > 0 && i % 3 == left) {
                    --rest;
                } else {
                    buffer.append(ch);
                }
            }
        }
        if (buffer.length() > 0 && buffer.charAt(buffer.length() - 1) == '0') {
            buffer = new StringBuffer("0");
        }
        return buffer.reverse().toString();
    }
}

golang 解法, 执行用时: 12 ms, 内存消耗: 6.1 MB, 提交时间: 2023-09-18 14:27:27

func largestMultipleOfThree(digits []int) string {
    cnt, total := [10]int{}, [3]int{}   // 分别统计0~9个数及3种余数的个数
    sum := 0
    for _, d := range digits {
        cnt[d]++
        total[d%3]++
        sum += d
    }

    rem := sum % 3  // 待删数的余数
    left := 0       // 需要删除的个数
    if rem != 0 {
        if total[rem] > 0 {
            left = 1    // 优先考虑删除一个数
        } else {
            rem = 3 - rem
            left = 2    // 删除两个数
        }
    }
    
    // 删除
    for i := 0; i < 10 && left > 0; i++ {
        for i % 3 == rem && cnt[i] > 0 && left > 0 {
            cnt[i]--
            left--
        }
    }
    
    ans := make([]byte, 0, len(digits))
    for i := 9; i >= 0; i-- {
        if i == 0 && len(ans) == 0 && cnt[0] > 0 {
            return "0"
        }
        for cnt[i] > 0 {
            ans = append(ans, byte(i) + '0')
            cnt[i]--
        }
    }

    return string(ans)
}

cpp 解法, 执行用时: 20 ms, 内存消耗: 19.3 MB, 提交时间: 2023-09-18 14:27:07

class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        vector<int> cnt(10), modulo(3);
        int sum = 0;
        for (int digit: digits) {
            ++cnt[digit];
            ++modulo[digit % 3];
            sum += digit;
        }

        int remove_mod = 0, rest = 0;
        if (sum % 3 == 1) {
            if (modulo[1] >= 1) {
                remove_mod = 1;
                rest = 1;
            }
            else {
                remove_mod = 2;
                rest = 2;
            }
        }
        else if (sum % 3 == 2) {
            if (modulo[2] >= 1) {
                remove_mod = 2;
                rest = 1;
            }
            else {
                remove_mod = 1;
                rest = 2;
            }
        }
        string ans;
        for (int i = 0; i <= 9; ++i) {
            for (int j = 0; j < cnt[i]; ++j) {
                if (rest && remove_mod == i % 3) {
                    --rest;
                }
                else {
                    ans += static_cast<char>(i + 48);
                }
            }
        }
        if (ans.size() && ans.back() == '0') {
            ans = "0";
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

python3 解法, 执行用时: 68 ms, 内存消耗: 16.4 MB, 提交时间: 2023-09-18 14:26:36

'''
能被3整除，则各位数字之和必定能被3整除。
s 为所有数字之和，
1、s能被3整除，则digits从大到小排序再连接；
2、s模3余1，从s中删除若干元素，其和也是模3余1。
从 digits 中删除一个最小的模 3 余 1 的数（例如 1，4，7）。
如果 digits 中没有这样的数，则删除两个最小的模 3 余 2 的数（例如 2，5，8）。
3、s模3余2，从 digits 中删除一个最小的模 3 余 2 的数，
如果没有这样的数，就删除两个最小的模 3 余 1 的数。

'''
class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        cnt, modulo = [0] * 10, [0] * 3
        s = 0
        for digit in digits:
            cnt[digit] += 1
            modulo[digit % 3] += 1
            s += digit
        
        remove_mod, rest = 0, 0
        if s % 3 == 1:
            remove_mod, rest = (1, 1) if modulo[1] >= 1 else (2, 2)
        elif s % 3 == 2:
            remove_mod, rest = (2, 1) if modulo[2] >= 1 else (1, 2)

        ans = ""
        for i in range(0, 10):
            for j in range(cnt[i]):
                if rest > 0 and remove_mod == i % 3:
                    rest -= 1
                else:
                    ans += str(i)
        if len(ans) > 0 and ans[-1] == "0":
            ans = "0"
        return ans[::-1]