如何在C++中以O(n)时间复杂度移除vector<string>元素中的逗号

API 探路者

2026-8-18

解决方案

可以通过一次遍历所有字符，过滤掉逗号后重新生成每个字符串，整体时间复杂度为O(n)（n为所有字符串的总字符数），也能实现单循环处理。以下是两种可行实现：

嵌套循环（逻辑上的总线性遍历）

这种写法直观，总操作数等于所有字符的总数，符合O(n)时间复杂度要求：

#include <vector>
#include <string>

int main() {
    std::vector<std::string> matrix = {"1,2,3", "4,5,6", "7,8,9"};
    
    for (auto& str : matrix) {
        std::string new_str;
        // 预分配空间，避免频繁内存扩容开销
        new_str.reserve(str.size() / 2 + 1);
        for (char c : str) {
            if (c != ',') {
                new_str += c;
            }
        }
        // 高效替换原字符串，避免大内存拷贝
        str.swap(new_str);
    }

    // 此时 matrix[0][1] 的值为 '2'
    return 0;
}

纯单循环实现

如果严格要求用单个循环完成所有操作，可以用如下写法，本质还是遍历所有字符，时间复杂度仍为O(n)：

#include <vector>
#include <string>

int main() {
    std::vector<std::string> matrix = {"1,2,3", "4,5,6", "7,8,9"};
    
    size_t str_idx = 0;
    size_t char_idx = 0;
    std::string new_str;
    while (str_idx < matrix.size()) {
        if (char_idx < matrix[str_idx].size()) {
            char c = matrix[str_idx][char_idx];
            if (c != ',') {
                new_str += c;
            }
            char_idx++;
        } else {
            matrix[str_idx].swap(new_str);
            new_str.clear();
            str_idx++;
            char_idx = 0;
        }
    }

    return 0;
}