C++中比对字符串首字符与其余字符如何降低时间复杂度

数据老陈

2026-10-4

C++字符串首字符比对性能优化方案

核心优化点

参数传递优化：原函数按值传递usernames会触发整个输入数组的深拷贝，输入规模大时开销极高，修改为const vector<string>& usernames常量引用传递，完全避免不必要的拷贝开销。
减少重复操作：每次循环前先提取当前字符串的首字符存为局部char变量，避免重复寻址取值；同时提前判断字符串长度，长度≤1时直接赋值为NO无需遍历。
替换手写循环为标准库算法：使用STL的std::any_of替代手写遍历，标准库算法内置了指令级优化（如SIMD向量化），开启编译优化后执行效率远高于普通手写循环。
固定返回值常量：提前定义"YES"和"NO"为静态常量字符串，避免每次赋值时生成临时字符串对象。

优化后代码

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<string> possibleChanges(const vector<string>& usernames) {
    static const string YES = "YES";
    static const string NO = "NO";
    int n = usernames.size();
    vector<string> answers(n);
    for(int i = 0; i < n; ++i) {
        const string& s = usernames[i];
        if(s.size() <= 1) {
            answers[i] = NO;
            continue;
        }
        char first = s[0];
        if(any_of(s.begin() + 1, s.end(), [first](char c) {
            return c < first;
        })) {
            answers[i] = YES;
        } else {
            answers[i] = NO;
        }
    }
    return answers;
}