优化移除数字生成可被3整除的最大数的算法时间复杂度

问题描述 #

给定一个长度为N（1≤N≤100）、仅由1-9组成的数字串，需移除至少1个数字，使剩余数字组成的数最大且能被3整除。

输入输出要求 #

• 输入：第1行是测试用例数量t（1≤t≤100），后续t行每行一个符合要求的数字串。
• 输出：每个测试用例输出满足条件的结果数，题目保证存在解。

输入输出示例 #

输入：

2
12324524
5321

输出：

1324524
531

现有解法与性能问题 #

原解法基于“一个数可被3整除当且仅当其各位数字之和可被3整除”的性质，思路如下：

• 若数字和无法被3整除，最多移除2个数字；
• 若数字和可被3整除，但需移除至少1个数字且无法通过移除1或2个数字满足，则需移除3个数字。

对应的代码通过暴力枚举所有移除1、2、3个数字的组合来更新最大结果：

void check(string s)
{
    int n = s.size();
    string res = "0";
    int sum = 0;
    for (int i = 0; i < n; i++) sum += s[i] - '0';
    bool f = 0, f1 = 0;
    for (int i = 0; i < n; i++)
    {
        if ((sum - (s[i] - '0')) % 3 == 0)
        {
            f = 1;
            string cur = "";
            for (int j = 0; j < n; j++)
            if(j != i) cur += s[j];
            res = max(res, cur);
        }
    }
    if (!f)
    {
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                if ((sum - (s[i] - '0') - (s[j] - '0')) % 3 == 0)
                {
                    f1 = 1;
                    string cur = "";
                    for (int k = 0; k < n; k++)
                        if (k != i && k != j) cur += s[k];
                    res = max(res, cur);
                }
            }
        }
    }
    if (!f && !f1)
    {
        for (int i = 0; i < n - 2; i++)
        {
            for (int j = i + 1; j < n - 1; j++)
            {
                for (int k = j + 2; k < n; k++)
                {
                    if ((sum - (s[i] - '0') - (s[j] - '0') - (s[k] - '0')) % 3 == 0)
                    {
                        string cur = "";
                        for (int t = 0; t < n; t++)
                            if (t != i && t != j && t != k) cur += s[t];
                        res = max(res, cur);
                    }
                }
            }
        }
    }
    cout << res << '\n';
}

但这段代码的时间复杂度为**O(n^{4)**，结合t个测试用例后总复杂度为O(t*n}4)。当t=100且n=100时，运行效率极低，需要针对性优化。

优化思路 #

核心是避免暴力枚举，利用数字模3的分类特性直接定位最优移除方案，步骤如下：

1. 分类统计数字模3情况

将数字串中的每个数字按模3结果分成三类：

• mod0：模3余0的数字列表
• mod1：模3余1的数字列表（按从小到大排序）
• mod2：模3余2的数字列表（按从小到大排序）
  计算所有数字总和total_sum，并求其模3结果remainder = total_sum % 3。

2. 确定最优移除组合

我们的目标是移除最少的数字（保证剩余数字长度最长），若有多种同数量移除方案，则移除最小的数字（保证剩余高位尽可能大）：

• 当remainder == 1时：
  • 优先移除1个mod1中最小的数字；
  • 若mod1为空，则移除2个mod2中最小的两个数字；
• 当remainder == 2时：
  • 优先移除1个mod2中最小的数字；
  • 若mod2为空，则移除2个mod1中最小的两个数字；
• 当remainder == 0时：
  • 因必须移除至少1个数字，优先移除1个最小的mod0数字；
  • 若mod0为空，则移除3个数字：选移除3个mod1最小项或3个mod2最小项中，剩余数字更大的方案（本质是移除更小的数字）；

3. 生成最大剩余数字

标记要移除的数字后，遍历原数字串，保留未被标记的数字即可得到最大结果（原串顺序保证了高位优先，移除最小数字后剩余串自然最大）。

4. 复杂度分析

整个过程的时间复杂度为O(n log n)（主要来自对mod1、mod2列表的排序），远低于原算法的O(n^4)，即使n=100、t=100也能高效运行。

内容的提问来源于stack exchange，提问作者tyghn