更多优质内容
请关注公众号

算法小白的入门日记(三十二)用什么数据结构实现随机抽奖——集合-张柏沛IT博客

正文内容

算法小白的入门日记(三十二)用什么数据结构实现随机抽奖——集合

栏目:算法专题 系列:算法小白的入门日记 发布时间:2022-01-28 21:04 浏览量:216
本系列文章目录
展开/收起

· 集合 set

集合是一个其内所存储的所有元素具有唯一性、随机性和无序性的复合型数据结构。


唯一性指所有元素不重复;

随机性指从集合中pop出一个元素时,集合内所有元素被pop出来的概率一样;

无序性指集合中的元素无序;


集合 set 这种数据结构被广泛引用,像python的set结构、redis的set结构 和 java 的 hashset结构,都具有上述特性。


下面我们通过一道题目看看 集合 set 结构如何实现。

力扣380. O(1) 时间插入、删除和获取随机元素

实现RandomizedSet 类:

RandomizedSet() 初始化 RandomizedSet 对象

bool insert(int val) 当元素 val 不存在时,向集合中插入该项,并返回 true ;否则,返回 false 。

bool remove(int val) 当元素 val 存在时,从集合中移除该项,并返回 true ;否则,返回 false 。

int getRandom() 随机返回现有集合中的一项(测试用例保证调用此方法时集合中至少存在一个元素)。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数,并满足每个函数的 平均 时间复杂度为 O(1) 。


实际上,集合的无序性和唯一性可以使用hashmap来实现,因为hashmap的key是无序的(准确的说是不按key的大小排序,而只按key被插入hashmap的时序排序),而且hashmap的key是唯一的,一个key不可能对应多个value。

以Go语言为例,用hashmap模拟一个整型集合,只需用hashmap的key存储集合的value,而hashmap的value存储空结构体即可。

type set map[int]struct{}


但是用 hashmap 实现的 set结构不具有随机性。原因很简单,随机选择一个元素需要用到类似于rand(n)的随机函数得到元素所在的位置(n是元素个数),而hashmap中的key是离散的,不是连续的。如果遍历hashmap并选择第rand(n)个元素作为元素是可以实现随机性的,但如此一来set集合的get方法复杂度就达到O(n)。

为了能实现O(1)的get,并且使用rand(n)获取随机元素的位置,元素必须是紧密存储的,因此需要用数组作为set的底层容器,通过数组 + rand(n) 实现set取出元素的随机性,通过hashmap实现set存储元素的无序性和唯一性。hashmap的key为集合的元素值,value为元素在数组的下标。


综上,set结构是一个 hashmap + 数组 的复合数据结构。



get() 操作只需从数组获取 arr[rand(n)] 元素即可获取到随机元素。

insert()操作只需往数组末尾添加元素,并在hashmap中添加元素。

delete()操作如果删除的是数组的中间元素,可以将数组的最后一个元素覆盖到被删除元素的位置,保持数组的元素依旧是紧密相连的。


代码实现如下:

import "math/rand"
type RandomizedSet struct {
    mp map[int]int
    arr []int
}
func Constructor() RandomizedSet {
    mp := make(map[int]int)
    arr := make([]int,0)
    return RandomizedSet{mp: mp, arr: arr}
}
func (this *RandomizedSet) Insert(val intbool {
    _, ok := this.mp[val]
    if ok{
        return false
    }
    this.arr = append(this.arr, val)
    this.mp[val] = len(this.arr) - 1
    return true
}
func (this *RandomizedSet) Remove(val intbool {
    _, ok := this.mp[val]
    if !ok{
        return false
    }
    valNum := len(this.arr)
    offset := this.mp[val]
    this.arr[offset], this.arr[valNum-1] = this.arr[valNum-1], this.arr[offset]
    this.mp[this.arr[offset]] = offset  // 修改被挪动位置的元素在mp中的值
    this.arr = this.arr[:valNum-1]  // 删除数组元素
    delete(this.mp, val)            // 删除hashmap元素
    return true
}
func (this *RandomizedSet) GetRandom() int {
    return this.arr[rand.Intn(len(this.arr))]
}



代码段 小部件



更多内容请关注微信公众号
zbpblog微信公众号

如果您需要转载,可以点击下方按钮可以进行复制粘贴;本站博客文章为原创,请转载时注明以下信息

张柏沛IT技术博客 > 算法小白的入门日记(三十二)用什么数据结构实现随机抽奖——集合

热门推荐
推荐新闻