RandomizedSet 数据结构类实现

项目背景

随机化集合数据结构是一种支持高效插入、删除和随机取元素操作的稀疏表数据结构。通过这种数据结构，开发者可以在保证操作时间复杂度为O(1)的前提下，实现对集合元素的高效管理。

实现思路

本实现使用 unordered_map 和 vector 两种数据结构协同工作。unordered_map 用于存储集合元素及其对应的索引信息，以支持O(1)时间复杂度的插入和删除操作。vector 则用于存储元素的实际值，方便随机取元素操作。

类成员变量定义

class RandomizedSet {private:    unordered_map
   
     mp;  // (value, index) 存储映射关系    vector
    
      vals;  // 存储元素值，便于随机取元素};

接下来是各个操作的实现

1. 插入操作

插入操作用于将一个值添加到集合中。如果集合中已经存在该值，则返回 false；否则，返回 true。

bool insert(int val) {    if (mp.find(val) != mp.end()) {        return false;  // 已存在，无法插入    }    mp[val] = vals.size();  // 记录值的索引位置    vals.push_back(val);     // 将值添加到数组末尾    return true;             // 插入成功}

2. 删除操作

删除操作用于移除集合中的一个值。如果集合中不存在该值，则返回 false；否则，返回 true。

bool remove(int val) {    if (mp.find(val) == mp.end()) {        return false;  // 不存在该值，无法删除    }    int index = mp[val];  // 获取该值在数组中的索引位置    // 交换当前值与数组最后一个元素的位置    swap(vals[index], vals.back());    // 删除数组最后一个元素（即当前值）    vals.pop_back();    // 更新映射关系：将被删除的值的索引位置设置为已删除的位置    mp[vals.back()] = index;    // 最终删除映射中的该值    mp.erase(val);    return true;  // 删除成功}

3. 随机取元素操作

随机取元素操作用于从集合中随机获取一个元素。通过 vector 的随机性，这个操作的时间复杂度为O(1)。

int getRandom() {    int index = rand() % vals.size();  // 取随机索引    return vals[index];               // 返回对应的值}

使用示例

// 初始化随机化集合对象RandomizedSet* obj = new RandomizedSet();// 插入元素bool insertResult = obj->insert(10);cout << "插入结果：" << (insertResult ? "成功" : "失败") << endl;// 删除元素bool deleteResult = obj->remove(10);cout << "删除结果：" << (deleteResult ? "成功" : "失败") << endl;// 随机取元素int randomValue = obj->getRandom();cout << "随机取到的元素值：" << randomValue << endl;

优势分析

插入与删除操作：通过 unordered_map 记录元素的位置信息，确保插入和删除操作均为O(1)时间复杂度。

随机取元素：利用 vector 存储元素，随机取索引实现高效随机访问。

内存占用：由于使用稀疏存储方式，内存占用率较低，适合处理大规模数据。

总结

本实现通过结合 unordered_map 和 vector 两种数据结构，设计了一种高效的随机化集合数据结构。该结构在插入、删除和随机取元素方面均具备较低的时间复杂度，适合处理大规模数据集中的稀疏集合操作。

转载地址：http://anrfk.baihongyu.com/

你可能感兴趣的文章