题解 | #找位置#

#include<bits/stdc++.h>

using namespace std;

int main() {
    string s;
    map<char, vector<int>> sm;
    vector<char> orderS;
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        if (sm.find(s[i]) != sm.end()) {
            sm[s[i]].push_back(i);
        } else {
            sm[s[i]] = vector<int>{i};
            orderS.push_back(s[i]);
        }
    }
    for (char item: orderS) {
        auto tmp = sm.find(item);
        if (tmp != sm.end() && tmp->second.size() > 1) {
            for (int index: tmp->second) {
                if (index != tmp->second.back())
                    cout << tmp->first << ':' << index << ',';
                else
                    cout << tmp->first << ':' << index << endl;
            }
        }
    }
}

时间复杂度为O(n)

1. 用一个额外的矢量orderS不重复的添加字符，以保证输出时字符顺序
2. 用map的key记录字符，value记录重复出现的次数
3. 最后按照orderS的顺序遍历输出