算法1

使用string的insert函数 $O(n^2)$

几个月之前刚学STL自己刷的时候自己乱写的，大概就是不停在每次倒数第三个位置上insert一个’,’，非常不推荐这种写法，insert的时间复杂度$O(N)$

C++ 代码

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    string result;
    int a, b, c;
    scanf("%d %d", &a, &b);
    c = a + b;
    result = to_string(abs(c));
    for (int i = 1; i * 3 < result.size() - i + 1; i++)
    {
        result.insert(result.size() - 4 * i + 1, 1, ',');
    }
    if (c < 0)
        printf("-");
    printf("%s", result.c_str());
}

算法2

顺序表插入 $O(n^2)$

大约一年多前学C语言时写的算法(那时候还不会C++)

C 代码

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
int main(void)
{
    int a, b;
    scanf("%d %d", &a, &b);
    char C[MAXSIZE];
    sprintf(C, "%d", a + b);
    int M = 0;
    while (C[M] != '\0')M++;
    int N = M;
    if (a + b > 0)
    {
        for (int n = 1; (M - 3 * n) > 0; n++)
        {
            for (int m = N - 1; m >= M - 3 * n; m--)
                C[m + 1] = C[m];
            C[M - 3 * n] = ','; N++;
        }
    }
    else
    { 
        for (int n = 1; (M - 3 * n) > 1; n++)
        {
            for (int m = N - 1; m >= M - 3 * n; m--)
                C[m + 1] = C[m];
            C[M - 3 * n] = ','; N++;
        }
    }
    C[N] = '\0';
    printf("%s", C);
    system("pause");
}

算法3

大佬算法 $O(n)$

• 思路很清晰，输入和输出用不同的字符串，写起来看起来都很清爽，并且算法复杂度降低了(insert复杂度应该是$o(n)$)
• 学到一个小技巧：res=num[i]+res,可以在字符串前面添加字符。

时间复杂度

O(N)

参考文献

PAT甲级辅导课

C++ 代码

int main()
{
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    int a, b, c;
    cin >> a >> b;
    c = a + b;
    string num = to_string(c);
    string res;
    for (int i = num.size() - 1, j = 0; i >= 0; i--)
    {
        res = num[i] + res;
        j++;//j++一定要写在这里！
        if (j % 3 == 0 && i && num[i - 1] != '-')res = ',' + res;
    }
    cout << res;
}