减少在 C++ 中比较一个字符串中的两个字符的时间复杂度

Question

我必须在 C++ 中比较字符串的第一个字母和字符串的其他字母例如：在“bsadasdaddgkoj”中我必须将 b 即第一个字母与所有其他字母进行比较，看看它是否按字母顺序更小但我必须非常快地做到这一点

vector<string> possibleChanges(vector<string> usernames) {
int n=usernames.size();
 vector<string> answers(n);
 for(int i=0;i<n;i++) {
     for(int j=1;j<usernames[i].size();j++) {
        if(usernames[i][0] > usernames[i][j]){
            answers[i] = "YES";
            break;
        }
    }
    if(answers[i]!="YES") answers[i]="NO";
 }
 return answers;
}

到目前为止我已经尝试过了，但确实很慢。

Answer 1

假设您确实需要字符串形式的答案...

vector<string> possibleChanges(const vector<string>& usernames) {
 const size_t n = usernames.size();
 vector<string> answers(n, "NO");
 for (size_t i = 0; i < n; ++i) {
    auto firstChar = usernames[i][0];
    auto it = std::find_if(usernames[i].begin() + 1, usernames[i].end(), [&firstChar](std::string::value_type ch) { return firstChar > ch; });
    if (it != usernames[i].end())
       answers[i] = "YES";
 }
 return answers;
}

此外，如果您知道 usernames[i].size() >= 2（或 4、或 8...），您可以像这样应用循环展开：

for (size_t i = 0; i < n; ++i) {
         auto firstChar = usernames[i][0];
         size_t j = 1;
         bool flag = false;
         for (; j + 4 < usernames[i].size(); j += 4) {
            if (firstChar > usernames[i][j] ||
               firstChar > usernames[i][j + 1] ||
               firstChar > usernames[i][j + 2] ||
               firstChar > usernames[i][j + 3]) 
            {
               answers[i] = "YES";
               flag = true;
               break;
            }
               
         }
         for (; j < usernames[i].size() && !flag; ++j) {
            if (firstChar > usernames[i][j]) {
               answers[i] = "YES";
               break;
            }
         }

减少在 C++ 中比较一个字符串中的两个字符的时间复杂度

reducing time complexity of compare two characters in one single string in c++

c++

string

time

compare