如何加速0-1数组分离代码？求循环优化等提速方案

先给你提个紧急的bug：你内层的while(n>0)循环里，读取数字后没做n--，这会导致循环无限跑下去，程序直接卡死，得先把这个修了。

回到你的核心需求——提升速度。其实你的思路（统计0的数量，直接输出对应个数的0和1）已经很高效了，因为没浪费内存存整个数组。我们可以从输入、输出这两个最拖速度的环节入手优化，毕竟IO操作的开销远大于计算：

1. 修复输入逻辑，同时加快输入速度 #

你用scanf的方式有两个小问题：

• 别加\n在scanf("%d\n", ...)里！scanf读取整数时会自动跳过所有前置空白（换行、空格、制表符），加了\n反而会让程序等着下一个非空白字符，输入的时候容易出问题。
• 多次调用scanf读单个数字开销不小，尤其是数据量一大就慢。换成getchar()直接读字符会快很多，毕竟少了scanf的格式化解析开销。

修改后的输入逻辑大概是这样：

int original_n = n; // 先存下初始的n值，后面输出要用
int countzero = 0;
while (original_n-- > 0) {
    int c;
    // 先跳过所有空白字符（空格、换行）
    while ((c = getchar()) != EOF && (c == ' ' || c == '\n'));
    if (c == '0') countzero++;
    // 1不用管，我们只需要统计0的数量
}

2. 把输出速度拉满：减少IO调用次数 #

你现在用两个for循环逐个打印0和1，每次printf("0")都会触发一次系统IO调用，这是非常慢的。我们要把IO次数从n次降到2次甚至1次：

方案一：用printf的格式化技巧一次性输出 #

提前准备一个足够长的0和1字符串，然后用%.*s格式指定输出长度，一次printf就能输出所有的0或1：

// 准备足够长的0、1字符串（比如各30000个，覆盖大部分测试场景）
const char *zeros = "00000000000000000000000000000000000000000000000000"
                   "00000000000000000000000000000000000000000000000000"
                   "00000000000000000000000000000000000000000000000000";
const char *ones = "11111111111111111111111111111111111111111111111111"
                  "11111111111111111111111111111111111111111111111111"
                  "11111111111111111111111111111111111111111111111111";

// 输出countzero个0，再输出original_n - countzero个1
printf("%.*s%.*s\n", countzero, zeros, original_n - countzero, ones);

如果你的测试用例数组长度超过30000，把字符串拉长就行，复制几次很方便。

方案二：缓冲区一次性输出（速度最快） #

如果数组特别大，直接分配一个缓冲区，填好0和1后一次输出，IO次数最少：

char *buf = malloc(original_n + 1); // +1存换行符
if (!buf) {
    // 处理内存分配失败的情况，比如直接退出
    fprintf(stderr, "内存分配失败\n");
    return 1;
}
// 填充0和1
memset(buf, '0', countzero);
memset(buf + countzero, '1', original_n - countzero);
buf[original_n] = '\n';
// 一次性输出
printf("%s", buf);
free(buf);

这个方案速度最快，但要注意如果n特别大（比如1e6以上），malloc可能会失败，需要处理这种情况。

完整优化后的代码 #

把这些优化点整合起来，最终代码如下：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
    // 准备足够长的0、1字符串
    const char *zeros = "00000000000000000000000000000000000000000000000000"
                       "00000000000000000000000000000000000000000000000000"
                       "00000000000000000000000000000000000000000000000000";
    const char *ones = "11111111111111111111111111111111111111111111111111"
                      "11111111111111111111111111111111111111111111111111"
                      "11111111111111111111111111111111111111111111111111";

    int testCase;
    // 修复scanf格式，去掉多余的\n
    scanf("%d", &testCase);
    while (testCase-- > 0) {
        int n;
        scanf("%d", &n);
        int original_n = n;
        int countzero = 0;

        // 用getchar优化输入
        while (n-- > 0) {
            int c;
            while ((c = getchar()) != EOF && (c == ' ' || c == '\n'));
            if (c == '0') {
                countzero++;
            }
        }

        // 一次性输出所有0和1
        printf("%.*s%.*s\n", countzero, zeros, original_n - countzero, ones);
    }
    return 0;
}

这种优化思路的核心是减少IO操作次数和避免不必要的格式化解析，毕竟对于这种简单的任务，计算开销几乎可以忽略，大部分时间都花在输入输出上。

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