[编程题]删除字符串中出现次数最少的字符

喜欢ヅ旅行 2022-07-14 14:08 118阅读 0赞

> Talk is cheap, show me the code.

### 一、问题描述 ###

实现删除字符串中出现次数最少的字符，若多个字符出现次数一样，则都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。

**输入描述：**

> 字符串只包含小写英文字母, 不考虑非法输入，输入的字符串长度小于等于20个字节。

**输出描述：**

> 删除字符串中出现次数最少的字符后的字符串。

**输入例子：**

> abcdd

**输出例子：**

> dd

### 二、问题分析 ###

要删除长度最短字符，首先需要找到这些需要删除的字符集或者找到最短的字符长度。删除字符时可以根据最短字符长度去取舍字符这是最有效的方法，也可以一个个遍历删除对应的字符，但是效率比较低。存储输入的字符串的每个字符最好使用长度为26的字符数组，也可以使用vector但是比较麻烦。

**解题方式1：**

先把输入的字符串的每个字符保存在vector中，找到最短长度，然后找到需要删除的字符集，然后依次删除对应的字符。

#include <iostream>
    #include <vector>
    #include <string>
    #include <iterator>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        string s;
        while (cin >> s)
        {
            vector<char> vect1;
            vector<int> vect2;
            for (int i = 0; i < s.size(); i++)
            {
                vector<char>::iterator it = find(vect1.begin(), vect1.end(), s[i]);
                if (it == vect1.end())
                {
                    vect1.push_back(s[i]);
                    vect2.push_back(1);
                } else {
                    vect2[it - vect1.begin()]++;
                }
            }
            vector<char> del;
            int min = 20, num = 1;
            for (vector<int>::iterator it = vect2.begin(); it != vect2.end(); ++it)
            {
                if (*it < min)
                {
                    min = *it;
                    num = 1;
                    del.push_back(vect1[it - vect2.begin()]);
                } else if (*it == min) {
                    num++;
                    del.push_back(vect1[it - vect2.begin()]);
                }
            }
            string str;
            for (vector<char>::reverse_iterator it = del.rbegin(); it != (del.rbegin() + num); ++it)
            {
                for (int i = 0; i < s.size(); i++)
                {
                    if (s[i] != *it)
                    {
                        str += s[i];
                    }
                }
                s = str;
                str = "";
            }
            cout << s << endl;
    
        }
        return 0;
    }

**解题方式2：**

先把输入的字符串的每个字符对应的字符长度存储在长度为26的字符数组中，然后找到最短字符长度，最后根据最短字符长度输出删除全部最短字符后的字符串。

#include <iostream>
    #include <string>
    using namespace std;
    int main()
    {
        int i, m,min;
        int a[26];
        string str,temp;
        while (cin >> str)
        {
            for (int i = 0; i < 26; i++)
                a[i] = 0;
    
            m = str.size();
            for (i = 0; i<m; i++)
                a[str[i]-'a']++;
            min = a[str[0]-'a'];
            for (i = 0; i<m; i++)
            if (a[str[i] - 'a'] <= min)
                min = a[str[i]-'a'];
            for (i = 0; i < m; i++)
            if (a[str[i] - 'a'] > min)
                cout << str[i];
    
            cout << endl;
        }  
        return 0;
    }