如何在O(N)时间内原地替换字符数组中的指定字符为两个字符

这是个经典的原地数组修改问题，你的O(N²)解法应该是因为从前往后替换时频繁移动元素导致的——确实，这种思路在遇到多个目标字符时会产生大量重复操作。下面是满足O(N)时间复杂度的原地解法，核心思路是从后往前遍历+双指针，完全避免元素的重复移动：

核心步骤 #

1. 统计目标字符数量，计算最终数组长度
   首先遍历一次数组，统计目标字符（这里是'z'）的出现次数count_z。因为每个'z'要替换成两个'R'，所以最终数组的长度是原长度 + count_z（每个'z'多占用一个位置）。

2. 双指针从后往前复制/替换

   • 用old_ptr指向原数组的最后一个有效元素（原长度的末尾）
   • 用new_ptr指向最终数组的末尾（新长度的末尾）
   • 从后往前遍历：
     • 如果old_ptr指向的字符不是'z'，直接将它复制到new_ptr的位置，然后两个指针都左移一位
     • 如果是'z'，则在new_ptr和new_ptr-1的位置都放入'R'，然后new_ptr左移两位，old_ptr左移一位

这种方式下，每个元素只会被复制一次，彻底规避了从前往后替换时的重复移动开销，时间复杂度严格为O(N)。

代码示例（Python） #

def replace_target_with_two_chars(arr, target='z', replacement='R'):
    # 第一步：统计目标字符出现次数
    count_target = arr.count(target)
    original_length = len(arr)
    new_length = original_length + count_target
    
    # 扩展数组到目标长度（适配Python列表的动态特性）
    arr += [None] * count_target
    
    # 初始化双指针
    old_ptr = original_length - 1
    new_ptr = new_length - 1
    
    while old_ptr >= 0:
        if arr[old_ptr] == target:
            # 写入两个替换字符
            arr[new_ptr] = replacement
            arr[new_ptr - 1] = replacement
            new_ptr -= 2
        else:
            # 直接复制原字符
            arr[new_ptr] = arr[old_ptr]
            new_ptr -= 1
        old_ptr -= 1
    
    return arr

# 测试示例
test_arr = ['a','b','c','z','s','w','y','z','o']
result = replace_target_with_two_chars(test_arr)
print(result)
# 输出: ['a', 'b', 'c', 'R', 'R', 's', 'w', 'y', 'R', 'R', 'o']

复杂度说明 #

• 时间复杂度：O(N)。统计目标字符是O(N)，双指针遍历也是O(N)，总时间为线性级别。
• 空间复杂度：O(1)（除数组本身的必要扩展空间）。仅使用了几个指针变量，未开辟额外线性空间，完全符合原地算法要求。

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