2336.无限集中的最小数字

题目要出无限集中最小的数字,所以可以使用set存数字(自动排序),一个biggest存当前出过的最小数字+1,初始为1。

入元素

插入的num大于biggest则不管,小于biggest则存入set。

出元素

若set不为空,则出set的头元素(set升序排列,头元素最小);

若set为空,则出biggest,biggest++;

class SmallestInfiniteSet {
public:
    SmallestInfiniteSet() {
        
    }
    
    int popSmallest() {
        int sm = 0; 
        if(s.size()==0)
        {    
            sm = biggest;
            biggest++;
        }
        else
        {
            sm = *s.begin();
            s.erase(s.begin());
        }
        return sm;
    }
    
    void addBack(int num) {
        if(num>=biggest)
            return;
        else{
             s.insert(num);
        }
    }
private:
    int biggest = 1;
    set<int> s;
};

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet* obj = new SmallestInfiniteSet();
 * int param_1 = obj->popSmallest();
 * obj->addBack(num);
 */

std::set是一种关联容器,用于存储唯一且已排序的元素。

基于红黑树实现,因此插入、删除和查找操作的平均时间复杂度为O(log n)。

一、std::set的核心特性

  1. 元素唯一性:不允许重复元素,插入重复值会被忽略。
  2. 自动排序:元素默认按升序排列(可通过自定义比较器修改排序规则)。
  3. 不可修改元素:集合中的元素是const的,不能直接修改(需先删除再插入新值)。

二、基本用法

1. 头文件与命名空间
#include <set>       // 包含set容器
using namespace std; // 或显式使用std::set
2. 定义与初始化
// 1. 定义空集合(默认升序)
set<int> s1;

// 2. 初始化列表
set<int> s2 = {3, 1, 4, 1, 5}; // 自动去重并排序:{1, 3, 4, 5}

// 3. 复制构造
set<int> s3(s2);

// 4. 自定义排序(降序)
set<int, greater<int>> s4 = {3, 1, 4}; // {4, 3, 1}

三、常用操作

1. 插入元素insert
set<int> s;
s.insert(5);       // 插入单个元素
s.insert({2, 8});  // 插入初始化列表
s.insert(s.begin(), s.end()); // 插入另一个容器的区间
2. 删除元素erase
set<int> s = {1, 2, 3, 4};

s.erase(3);               // 删除值为3的元素(返回删除个数)
s.erase(s.begin());       // 删除迭代器指向的元素
s.erase(s.find(2), s.end()); // 删除[find(2), end())区间的元素
s.clear();                // 清空所有元素
3. 查找元素find
set<int> s = {1, 2, 3, 4};

// 1. 查找值为3的元素(返回迭代器)
auto it = s.find(3); 
if (it != s.end()) {
    cout << "找到元素:" << *it << endl;
}

// 2. 统计值为3的元素个数(只能是0或1)
int count = s.count(3); // 结果为1
4. 迭代器遍历((r)begin/(r)end)
set<int> s = {1, 2, 3, 4};

// 正向遍历(升序)
for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << " "; // 输出:1 2 3 4
}

// 反向遍历(降序)
for (auto it = s.rbegin(); it != s.rend(); ++it) {
    cout << *it << " "; // 输出:4 3 2 1
}
5. 边界操作:大于等于lower_bound/大于upper_bound/等于equal_range
set<int> s = {1, 3, 5, 7};

auto left = s.lower_bound(2);  // 指向 3(第一个≥2的元素)
auto right = s.upper_bound(5); // 指向 7(第一个>5的元素)
auto range = s.equal_range(4); // null(指向等于4的元素)

6. 其他常用方法
set<int> s = {1, 2, 3};
s.size();       // 返回元素个数(3)
s.empty();      // 判断是否为空(false)
s.max_size();   // 返回最大可容纳元素数

四、自定义类型与比较器

std::set存储自定义类型时,需指定排序规则(通过重载operator<或自定义比较器)。

存储自定义结构体
#include <string>

struct Person {
    string name;
    int age;
};

// 自定义比较器(按年龄升序)
struct CompareAge {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age; // 年龄小的在前
    }
};

// 定义使用自定义比较器的set
set<Person, CompareAge> people;

// 插入元素
people.insert({"Alice", 25});
people.insert({"Bob", 20}); // 自动按年龄排序:Bob(20) → Alice(25)

五、std::set与std::unordered_set的区别

特性std::setstd::unordered_set
底层实现红黑树哈希表
排序自动排序无序
查找效率O(log n)平均 O (1),最坏 O (n)
适用场景需要排序或范围查询只需快速查找、插入删除

六、注意事项

  1. std::set的元素是const的,不能直接修改(如*it = 5是错误的)。
  2. 插入已存在的元素会被忽略,可通过insert的返回值判断是否插入成功:
    auto [it, inserted] = s.insert(3); 
    if (inserted) {
        cout << "插入成功" << endl;
    } else {
        cout << "元素已存在" << endl;
    }
    
  3. 自定义比较器必须满足严格弱序(避免逻辑错误)。
Logo

码道开发者社区,聚焦华为云码道 CodeArts 代码智能体,沉淀 Agent、Skill、鸿蒙开发实战内容,供开发者查阅资料、交流技术、分享工程实践

更多推荐