题目的主要信息：

实现删除字符串中出现次数最少的字符，若多个字符出现次数一样，则都删除
输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序
输入只包含26个英文字母
输入的字符串长度小于等于20个字节

方法一：暴力解法

具体做法：

我们可以利用vector中嵌套pair数组来记录字符及其出现的次数。遍历字符串，对每个字符在数组中查找是否出现过了，如果是直接在次数上加1，如果不是则在末尾添加这一项。完成以后，用重载的大小比较，按照出现次数排序，使之成为一个递增序。然后我们遍历这个数字，找到出现次数的次小值的下标，之后就是遍历字符串，每次遍历数组开始到次小值之间，查看该字符有无其在中，如果有，则不输出，否则正常输出。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

bool comp(pair<char, int>& a, pair<char, int>& b){ //重载比较
    return a.second < b.second; 
}

int main(){
    string s;
    while(cin >> s){
        vector<pair<char, int> > record;
        for(int i = 0; i < s.length(); i++){
            int j = 0;
            for(; j < record.size(); j++) //遍历记录数组
                if(record[j].first == s[i]){ //要是出现过
                    record[j].second++; //直接添加次数
                    break;
                }
            if(j == record.size()) //否则push新的字符
                record.push_back(make_pair(s[i], 1));
        }
        sort(record.begin(), record.end(), comp); //对出现次数排序
        int minindex = record.size();
        for(int i = 1; i < record.size(); i++){
            if(record[i].second > record[0].second){ //找到第一个不是最少次数的下标
                minindex = i;
                break;
            }
        }
        for(int i = 0; i < s.length(); i++){
            bool flag = false;
            for(int j = 0; j < minindex; j++){ //遍历所有的最少次数
                if(s[i] == record[j].first){ //检查s[i]是否在其中
                    flag = true;
                    break;
                }
            }
            if(!flag) //不在其中则输出
                cout << s[i];
        }
        cout << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n^{2})$ ， $n$ 为字符串长度，记录出现次数和输出过程，最坏都是两层循环
空间复杂度： $O (1)$ ，26个字母，辅助数组最长为26，常数空间

方法二：哈希

具体做法：

因为只有26个字母，因此我们可以用哈希的方式，数组下标0-25分别代替'a'-'z'，遍历字符串直接在其中记录字符出现的次数，然后再遍历这个哈希数组，找到最小的且不是0的元素，因此0是没出现过的字符，不用管。最后遍历字符串，顺序输出所有在上面哈希数组中大于刚刚找到的最小值的字符即可。

alt

#include<iostream>
#include<vector>
#include<string>
using namespace std;

int main(){
    string s;
    while(cin >> s){
        vector<int> count(26, 0); //记录字母出现的次数
        for(int i = 0; i < s.length(); i++) //遍历字符串
            count[s[i] - 'a']++; //统计每个字母出现的次数
        int min = count[s[0] - 'a']; //以第一个出现的字符为始
        for(int i = 0; i < 26; i++)
            if(min > count[i] && count[i] > 0) //一定要找到最小但不是0的次数
                min = count[i];
        for(int i = 0; i < s.length(); i++) //输出所有出现次数大于min的字符
            if(count[s[i] - 'a'] > min)
                cout << s[i];
        cout << endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n)$ ， $n$ 为字符串长度，所有遍历都是单层循环
空间复杂度： $O (1)$ ，哈希数组的长度为26，属于常数空间

题解 | #删除字符串中出现次数最少的字符#

题目的主要信息：

方法一：暴力解法

方法二：哈希