题解 | 【模板】多重集合操作

C++为提高查找效率，采用map（底层是红黑树，时间复杂度 O (log n)）或multiset

#include<bits/stdc++.h>
using namespace std;

class multiSet {
    private:
    map<int, int> val_num;
    int totalnum=0;
    public:
    void insertValue(int x){
        //TODO 实现插入逻辑
        val_num[x]++;
        totalnum++;        
    }
    void eraseValue(int x){
        //TODO 实现删除逻辑
        auto it = val_num.find(x);
        if (it==val_num.end()) return;
        if (--(it->second)==0) {
            val_num.erase(it);
        }
        totalnum--;
    }
    int xCount(int x){
        //TODO 求x在集合中的个数
        auto it = val_num.find(x);
        return (it!=val_num.end())?it->second:0;
    }
    int sizeOfSet(){
        //TODO 返回集合大小
        return totalnum;
    }
    int getPre(int x){
        //TODO 实现找前驱
        auto it = val_num.lower_bound(x); // >=x
        if (it==val_num.begin()) return -1;
        --it;
        return it->first;
    }
    int getBack(int x){
        //TODO 实现找后继
        auto it = val_num.upper_bound(x); // >x
        if (it==val_num.end()) return -1;
        return it->first;
    }
};

int main(){
    int q,op,x;
    cin>>q;
    multiSet M;
    while(q--){
        cin>>op;
        if(op==1){
            cin>>x;
            M.insertValue(x);
        }
        if(op==2){
            cin>>x;
            M.eraseValue(x);
        }
        if(op==3){
            cin>>x;
            cout<<M.xCount(x)<<endl;
        }
        if(op==4){
            cout<<M.sizeOfSet()<<endl;
        }
        if(op==5){
            cin>>x;
            cout<<M.getPre(x)<<endl;
        }
        if(op==6){
            cin>>x;
            cout<<M.getBack(x)<<endl;
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

class multiSet {
    private:
    multiset<int> val_num;
    public:
    void insertValue(int x){
        //TODO 实现插入逻辑
        val_num.insert(x); 
    }
    void eraseValue(int x){
        //TODO 实现删除逻辑
        auto it = val_num.find(x);
        if (it!=val_num.end()) val_num.erase(it);
    }
    int xCount(int x){
        //TODO 求x在集合中的个数
        return val_num.count(x);
    }
    int sizeOfSet(){
        //TODO 返回集合大小
        return val_num.size();
    }
    int getPre(int x){
        //TODO 实现找前驱
        auto it = val_num.lower_bound(x); // >=x
        if (it==val_num.begin()) return -1;
        --it;
        return *it;
    }
    int getBack(int x){
        //TODO 实现找后继
        auto it = val_num.upper_bound(x); // >x
        if (it==val_num.end()) return -1;
        return *it;
    }
};

int main(){
    int q,op,x;
    cin>>q;
    multiSet M;
    while(q--){
        cin>>op;
        if(op==1){
            cin>>x;
            M.insertValue(x);
        }
        if(op==2){
            cin>>x;
            M.eraseValue(x);
        }
        if(op==3){
            cin>>x;
            cout<<M.xCount(x)<<endl;
        }
        if(op==4){
            cout<<M.sizeOfSet()<<endl;
        }
        if(op==5){
            cin>>x;
            cout<<M.getPre(x)<<endl;
        }
        if(op==6){
            cin>>x;
            cout<<M.getBack(x)<<endl;
        }
    }
    return 0;
}

采用顺序链表，查找时间复杂度为O(n)，在输入q=100000时会超时

#include<bits/stdc++.h>
using namespace std;

class multiSet {
    private:
    struct Node {
        int val;
        int num=1;
        Node *next=nullptr;
        Node(int val) : val(val) {}
    };
    Node *head=new Node(-1);
    int totalnum=0;
    public:
    void insertValue(int x){
        //TODO 实现插入逻辑
        Node *p=head;
        while (p->next && p->next->val<x) {
            p = p->next;
        }
        if (p->next && p->next->val==x) {
            p->next->num++;
        }
        else {
            Node *q = new Node(x);
            q->next = p->next;
            p->next = q;
        }
        totalnum++;        
    }
    void eraseValue(int x){
        //TODO 实现删除逻辑
        Node *p=head;
        while (p->next) {
            if (p->next->val==x) {
                if (p->next->num==1) {
                    Node *t = p->next;
                    p->next = t->next;
                    delete t;
                }
                else {
                    p->next->num--;
                }
                totalnum--;
                return;
            }
            p = p->next;
        }
    }
    int xCount(int x){
        //TODO 求x在集合中的个数
        Node *p=head;
        while (p->next) {
            if (p->next->val==x) {
                return p->next->num;
            }
            p = p->next;
        }
        return 0;
    }
    int sizeOfSet(){
        //TODO 返回集合大小
        return totalnum;
    }
    int getPre(int x){
        //TODO 实现找前驱
        Node *p=head;
        while (p->next && p->next->val<x) {
            p = p->next;
        }
        return p->val;
    }
    int getBack(int x){
        //TODO 实现找后继
        Node *p=head;
        while (p->next && p->next->val<=x) {
            p = p->next;
        }
        if (p->next) return p->next->val;
        return -1;
    }
};

int main(){
    int q,op,x;
    cin>>q;
    multiSet M;
    while(q--){
        cin>>op;
        if(op==1){
            cin>>x;
            M.insertValue(x);
        }
        if(op==2){
            cin>>x;
            M.eraseValue(x);
        }
        if(op==3){
            cin>>x;
            cout<<M.xCount(x)<<endl;
        }
        if(op==4){
            cout<<M.sizeOfSet()<<endl;
        }
        if(op==5){
            cin>>x;
            cout<<M.getPre(x)<<endl;
        }
        if(op==6){
            cin>>x;
            cout<<M.getBack(x)<<endl;
        }
    }
    return 0;
}