题解 | 【模板】集合操作

C++

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

class Set {
  private:
    array<int, 100000> s;
    int len=0;
  public:
    void insertValue(int x) {
        //TODO 实现插入逻辑
        if (!xInSet(x)) {
            if (!len) {
                s[0] = x;
                len++;
                return;
            }
            int k=len-1;
            for (; k>-1 && s[k] > x; k--) {
                s[k+1] = s[k];
            }
            s[k+1] = x;
            len++;
        }
    }
    void eraseValue(int x) {
        //TODO 实现删除逻辑
        int k=0;
        for (; k<len; k++) if (s[k]==x) break;
        if (k==len) return;
        for (; k<len-1; k++) s[k]=s[k+1]; 
        len--;
    }
    int xInSet(int x) {
        //TODO 实现存在性检查
        int k=0;
        for (; k<len; k++) if (s[k]==x) return 1;
        return 0;
    }
    int sizeOfSet() {
        //TODO 返回集合大小
        return len;
    }
    int getPre(int x) {
        //TODO 实现找前驱 - 可以是集合最后一个元素
        int f = -1;
        for (int k=0; k<len && s[k]<x; k++) {
            f=s[k];
        }
        return f;
    }
    int getBack(int x) {
        //TODO 实现找后继 - 可以是集合第一个元素
        int f = -1;
        for (int k=len-1; k>-1 && s[k]>x; k--) {
            f=s[k]; 
        }
        return f;
    }
};

int main() {
    int q, op, x;
    cin >> q;
    Set 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;
            if (M.xInSet(x)) {
                cout << "YES\n";
            } else {
                cout << "NO\n";
            }
        }
        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;
}