求O(n)时间复杂度的原地相同字符模式压缩算法

嘿，这个问题我当初面试也碰到过，单个字符要加“1”的处理确实容易卡壳！咱们来拆解下怎么搞定这个原地压缩的需求，保证O(n)时间和O(1)空间，完全符合要求。

核心痛点拆解 #

你说的问题特别典型：从前往后处理时，单个字符要插入“1”就得前移后面的字符，直接把时间复杂度搞成O(n²)了。根本原因是从前往后写会覆盖还没扫描的字符——尤其是当压缩后的长度比原字符长的时候（比如单个字符从1位变2位）。那换个方向，从后往前处理就能完美避开这个坑！

具体实现步骤 #

第一步：先算好压缩后的总长度

首先得遍历一遍原字符串，统计每个连续字符块的长度，算出压缩后需要的总长度（每个块的数字位数 + 1个字符位）。比如：

• 原串abc每个字符都是1次，总长度就是2+2+2=6
• 示例里的abbbccccdee总长度是2+2+2+2+2=10

这一步是线性遍历，O(n)时间，完全不需要额外空间。

第二步：从后往前原地写入压缩结果

初始化两个指针：write_ptr从压缩后的总长度末尾开始，scan_ptr从原字符串的末尾开始，从后往前扫：

1. 找到当前字符的连续长度：比如从末尾的e开始，往前扫直到遇到不是e的字符，统计出连续2个e
2. 先把字符写到write_ptr的位置，然后指针左移一位
3. 再把数字（比如2）转换成字符，从个位开始逐个写到write_ptr位置，每写一个左移一位
4. 重复这个过程直到处理完所有字符

这样做的好处是：write_ptr永远在scan_ptr的左边，只会覆盖已经扫描过的、不再需要的字符，绝对不会干扰还没处理的部分。

代码示例（C语言） #

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

void compress(char* s) {
    int n = strlen(s);
    if (n == 0) return;

    // 第一步：计算压缩后的总长度
    int compressed_len = 0;
    int i = 0;
    while (i < n) {
        char current = s[i];
        int count = 0;
        while (i < n && s[i] == current) {
            count++;
            i++;
        }
        // 统计数字的位数（比如100是3位，5是1位）
        int digit_len = 0;
        int temp = count;
        do {
            digit_len++;
            temp /= 10;
        } while (temp > 0);
        compressed_len += digit_len + 1; // 数字位数 + 字符位
    }

    // 第二步：从后往前写入压缩结果
    int write_ptr = compressed_len - 1;
    i = n - 1;
    while (i >= 0) {
        char current = s[i];
        int count = 0;
        while (i >= 0 && s[i] == current) {
            count++;
            i--;
        }
        // 先写字符
        s[write_ptr--] = current;
        // 再写数字（从个位开始写）
        int temp = count;
        do {
            s[write_ptr--] = '0' + (temp % 10);
            temp /= 10;
        } while (temp > 0);
    }

    // 给字符串加结束符（原数组足够大的前提下）
    s[compressed_len] = '\0';
}

int main() {
    char s[20] = "abbbccccdee";
    printf("原字符串：%s\n", s);
    compress(s);
    printf("压缩后：%s\n", s);
    return 0;
}

为什么这个方案符合要求？ #

• 时间复杂度O(n)：两次线性遍历，统计长度和写入都是O(n)，没有嵌套的移位操作
• 空间复杂度O(1)：只用了几个临时变量，完全原地修改，没有额外分配内存
• 完美解决单个字符问题：不需要插入或前移字符，直接覆盖已扫描的区域，彻底避免了复杂度升高的问题

你的原有思路其实方向是对的，但从前往后写的逻辑容易踩覆盖的坑，换个从后往前的角度，问题就迎刃而解啦！

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