题目描述

Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.

Since the answer may not fit in an integer data type, return the answer as a string.

If there is no answer return an empty string.

Example 1:

Input: digits = [8,1,9]
Output: "981"

Example 2:

Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:

Input: digits = [1]
Output: ""

Example 4:

Input: digits = [0,0,0,0,0,0]
Output: "0“ 

Constraints:

• 1 <= digits.length <= 10^4
• 0 <= digits[i] <= 9
• The returning answer must not contain unnecessary leading zeros.

题意：给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。如果无法得到答案，请返回一个空字符串。

算法1

(计数，枚举) $O(n)$

我们都知道如果一个数字能够整除3，那么各位数字之和也可以整除3。我们先计算出所有数字的和，然后分三种情况讨论：

• 数组和恰好是3的倍数，那么我们只需要将所有的数字从大到小拼接起来即可。
• 数组和除以3余1，为了使得数字最大，我们需要删除一个[1,4,7]当中的数字，如果找不到，我们就删除两个[2,5,8]当中的数字。
• 数组和除以3余2，为了使得数字最大，我们需要删除一个[2,5,8]当中的数字，如果找不到，我们就删除两个[1,4,7]当中的数字。

我们只需要将剩余的数字从大到小排序即可，此外还需要注意答案可能是空串，去除前导0。还有数据范围是在0-9之间，根本没有必要排序，只需要进行计数即可。所以总的时间复杂度就是统计每个数字出现次数，$O(n )$

    string largestMultipleOfThree(vector<int>& digits) {
        int n = digits.size(),sum = 0;
        vector<int> cnts(10,0);
        for(int i = 0 ; i < n ; i ++)
        {
            cnts[digits[i]] ++;
            sum += digits[i];
        }
        if(sum % 3 == 1)
        {
            bool flag = false;
            for(int i = 1 ; i < 10 ; i += 3)
            {
                if(cnts[i] > 0)
                {
                    cnts[i] --;
                    flag = true;
                    break;
                }
            }
            if(!flag)
            {
                int cnt = 2;
                for(int i = 2 ; i < 10 ; i += 3)
                {
                    while(cnts[i] > 0)
                    {
                        cnts[i] --;
                        cnt --;
                    }
                    if(cnt == 0)
                        break;
                }
            }
        }else if(sum % 3 == 2)
        {
            bool flag = false;
            for(int i = 2 ; i < 10 ; i += 3)
            {
                if(cnts[i] > 0)
                {
                    cnts[i] --;
                    flag = true;
                    break;
                }
            }
            if(!flag)
            {
                int cnt = 2;
                for(int i = 1 ; i < 10 ; i += 3)
                {
                    while(cnts[i] > 0)
                    {
                        cnts[i] --;
                        cnt --;
                    }
                    if(cnt == 0)
                        break;
                }
            }
        }
        string res = "";
        for(int i = 9 ; i > 0 ; i --)
            for(int j = 0 ; j < cnts[i] ; j ++)
                res.push_back('0' + i);
        if(res.length() == 0)
        {
            if(cnts[0] == 0) return "";
            else return "0";
        }
        for(int j = 0 ; j < cnts[0] ; j ++)
            res.push_back('0');
        return res;
    }