前言

其实完全可以不用这么麻烦，我就是为了练习自建堆，其实大材小用

描述

实现删除字符串中出现次数最少的字符，若多个字符出现次数一样，则都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。
注意每个输入文件有多组输入，即多个字符串用回车隔开

输入描述：

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

输出描述：

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

解法

#include <iostream>
#include <sstream>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;

class MyHeap{
private:
    vector<char> arr; //堆数组
    unordered_map<char, int> indexMap; //记录索引
    unordered_map<char, int> numMap; //出现了几次
    int size; //堆的大小
public:
    explicit MyHeap(int s);
    void swap(int pos1, int pos2);
    bool empty() const;
    bool isEntered(char &c);
    bool isInHeap(char &c);
    char pop();
    void heapInsert(int index);
    void heapfiy(int index);
    void updateOrIgnore(char c);
    int checkNum();
};
MyHeap::MyHeap(int s) {
    size = 0;
    arr.resize(s);
}
bool MyHeap::empty() const {
    return size == 0;
}
bool MyHeap::isEntered(char &c) {
    return indexMap.find(c) != indexMap.end();
}
bool MyHeap::isInHeap(char &c) {
    return isEntered(c) && indexMap[c] != -1;
}
void MyHeap::swap(int pos1, int pos2) {
    indexMap[arr[pos1]] = pos2;
    indexMap[arr[pos2]] = pos1;
    char temp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = temp;
}

void MyHeap::heapInsert(int index) {
    while(index > 0 && numMap[arr[index]] < numMap[arr[(index-1)/2]]){
        swap(index, (index-1)/2);
        index = (index-1)/2;
    }
}

void MyHeap::heapfiy(int index) {
    int left = 2 * index + 1;
    while(left < size){
        int smallIndex = (left+1 < size) && (numMap[arr[left]] > numMap[arr[left+1]])?
                left + 1:left;
        smallIndex = numMap[arr[index]] > numMap[arr[smallIndex]]?
                smallIndex:index;
        if(smallIndex == index){
            break;
        }
        swap(index, smallIndex);
        index = smallIndex;
        left = 2 * index + 1;
    }
}

void MyHeap::updateOrIgnore(char c) {
    if(!isEntered(c)){
        arr[size] = c;
        numMap[c] = 1;
        indexMap[c] = size;
        heapInsert(size++);
    }
    else if(isInHeap(c)){
        ++numMap[c];
        int index = indexMap[c];
        heapfiy(index);
    }
}

char MyHeap::pop(){
    char returnString = arr[0];
    indexMap[returnString] = -1;
    numMap.erase(returnString);
    swap(0, size - 1);
    arr[size-1] = 0;
    --size;
    heapfiy(0);
    return returnString;
}

int MyHeap::checkNum() {
    return numMap[arr[0]];
}

void solution(const string& s){
    MyHeap myHeap(20);
    for(auto &it:s){
        myHeap.updateOrIgnore(it);
    }
    vector<char> arr;
    int minNum = myHeap.checkNum();
    while(!myHeap.empty()){
        if(minNum < myHeap.checkNum()){
            break;
        }
        char it = myHeap.pop();
        arr.push_back(it);
    }
    for(auto it_:s){
        int flag = 0;
        for(auto it:arr){
            if(it == it_){
                flag = 1;
                continue;
            }
        }
        if(flag == 1) continue;
        cout<<it_;
    }
    cout<<endl;
}

int main() {
    string s;
    while(cin>>s){
        solution(s);
    }

    return 0;
}

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