C++并行向量开发问题：排序字符时无法正确生成对应值向量

错误点排查 #

你的代码存在两个关键问题，导致数值vector生成不符合预期：

1. 头部插入时的索引错误
   当插入到vector头部（index==0）时，你错误地访问了sorted_values[1]，但此时插入前sorted_values的长度为i（当前是第i+1次迭代），头部相邻元素应该是原vector的第一个元素sorted_values[0]，而非第二个元素。

2. 重复字符插入位置错误
   原循环条件while (index < sorted_chars.size() && c >= sorted_chars[index])会让所有等于当前字符的元素被跳过，导致新插入的重复字符被放在已有同字符的后方，违反了"重复字符放在已有同字符前方"的要求，应该改为c > sorted_chars[index]，这样遇到相等字符时就停止移动索引，插入到当前位置。

修复后的代码 #

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
    string input;
    cin>>input;
    vector<char> sorted_chars;
    vector<int> sorted_values;
    for (int i = 0; i < input.size(); i++) {
        char c = input[i];
        int index = 0;
        // 修改循环条件，确保重复字符插入到已有同字符前方
        while (index < sorted_chars.size() && c > sorted_chars[index]) {
            index++;
        }
        sorted_chars.insert(sorted_chars.begin() + index, c);
        int value;
        if(i==0){
            sorted_values.push_back(0);
        }
        else if(index == sorted_chars.size()-1){
            // 插入到尾部，取前一个元素值+1
            value = sorted_values[index - 1] + 1;
            sorted_values.insert(sorted_values.begin()+index, value);
        }
        else if(index == 0){
            // 插入到头部，取原头部元素值+1
            value = sorted_values[0] + 1;
            sorted_values.insert(sorted_values.begin()+index, value);
        }
        else{
            // 插入到中间，取左右相邻元素的较大值+1
            value = max(sorted_values[index-1], sorted_values[index]) + 1;
            sorted_values.insert(sorted_values.begin()+index, value);
        }
    }
    // 输出结果
    for(char ch : sorted_chars){
        cout<<ch;
    }
    cout<<"\n";
    for(int val : sorted_values){
        cout<<val<< " ";
    }    
}

验证结果 #

输入PYTHONN时，修复后的代码会生成符合预期的结果：

• 字符vector：HNNOPTY
• 数值vector：1 4 3 2 0 2 1

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