防城港网站设计,珠海市建设工程信息网,开发购物网站社交的软件公司,网站建设报价方案.xlsRandomizedSet结构体存在切片和哈希表的原因#xff1a; 变长数组由于可以根据下标定位到特定元素#xff0c;因此可以在 O(1)的时间内完成获取随机元素操作#xff0c;但是由于无法在 O(1) 的时间内判断元素是否存在#xff0c;因此不能在 O(1) 的时间内完成插入和删除操作…RandomizedSet结构体存在切片和哈希表的原因 变长数组由于可以根据下标定位到特定元素因此可以在 O(1)的时间内完成获取随机元素操作但是由于无法在 O(1) 的时间内判断元素是否存在因此不能在 O(1) 的时间内完成插入和删除操作。 哈希表可以在 O(1) 的时间内判断元素是否存在因此可以在 O(1)的时间内完成插入和删除操作但是不可以根据下标定位到特定元素因此不能在 O(1) 的时间内完成获取随机元素操作。 为了满足插入、删除和获取随机元素操作的时间复杂度都是 O(1)需要将变长数组和哈希表结合变长数组中存储元素哈希表中存储每个元素在变长数组中的下标。 O(1) 时间插入、删除和获取随机元素 实现RandomizedSet 类 RandomizedSet() 初始化 RandomizedSet 对象 bool insert(int val) 当元素 val 不存在时向集合中插入该项并返回 true 否则返回 false 。 bool remove(int val) 当元素 val 存在时从集合中移除该项并返回 true 否则返回 false 。 int getRandom() 随机返回现有集合中的一项测试用例保证调用此方法时集合中至少存在一个元素。每个元素应该有 相同的概率 被返回。 你必须实现类的所有函数并满足每个函数的 平均 时间复杂度为 O(1) 。 示例 输入 [“RandomizedSet”, “insert”, “remove”, “insert”, “getRandom”, “remove”, “insert”, “getRandom”] [[], [1], [2], [2], [], [1], [2], []] 输出 [null, true, false, true, 2, true, false, 2] 解释 RandomizedSet randomizedSet new RandomizedSet(); randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。 randomizedSet.remove(2); // 返回 false 表示集合中不存在 2 。 randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。 randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。 randomizedSet.remove(1); // 从集合中移除 1 返回 true 。集合现在包含 [2] 。 randomizedSet.insert(2); // 2 已在集合中所以返回 false 。 randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字getRandom 总是返回 2 。 type RandomizedSet struct {nums []intindices map[int]int
}func Constructor() RandomizedSet {return RandomizedSet{nums: make([]int, 0),indices: make(map[int]int),}
}func (this *RandomizedSet) Insert(val int) bool {if _, ok : this.indices[val]; ok {return false}// 在变长数组的末尾添加 valthis.nums append(this.nums, val)//在添加 val 之前的变长数组长度为 val所在下标 index将 val和下标 index 存入哈希表// 因为要保证插入的值唯一因此需要放在key的位置this.indices[val] len(this.nums) - 1return true
}func (this *RandomizedSet) Remove(val int) bool {idx, ok : this.indices[val]if !ok {return false}lastIdx : len(this.nums) - 1lastVal : this.nums[lastIdx]this.nums[idx] lastValthis.indices[lastVal] idxdelete(this.indices, val)this.nums this.nums[:lastIdx]return true
}func (this *RandomizedSet) GetRandom() int {randIdx : rand.Intn(len(this.nums))return this.nums[randIdx]
}// 变长数组可以在 O(1)的时间内完成获取随机元素操作但是由于无法在 O(1) 的时间内判断元素是否存在因此不能在 O(1) 的时间内完成插入和删除操作。哈希表可以在 O(1)的时间内完成插入和删除操作但是由于无法根据下标定位到特定元素因此不能在 O(1) 的时间内完成获取随机元素操作。
//为了满足插入、删除和获取随机元素操作的时间复杂度都是 O(1)需要将变长数组和哈希表结合变长数组中存储元素哈希表中存储每个元素在变长数组中的下标。/**1. Your RandomizedSet object will be instantiated and called as such:2. obj : Constructor();3. param_1 : obj.Insert(val);4. param_2 : obj.Remove(val);5. param_3 : obj.GetRandom();*/插入操作时首先判断 val是否在哈希表中如果已经存在则返回 false如果不存在则插入 val操作如下 在变长数组的末尾添加 val 在添加 val之前的变长数组长度为 val所在下标 index将 val\textit{val}val 和下标 index 存入哈希表 返回 true。删除操作时首先判断 val是否在哈希表中如果不存在则返回 false如果存在则删除 val操作如下 从哈希表中获得 val的下标 index 将变长数组的最后一个元素 last移动到下标 index处在哈希表中将 last 的下标更新为 index 在变长数组中删除最后一个元素在哈希表中删除 val 返回 true。
删除操作的重点在于将变长数组的最后一个元素移动到待删除元素的下标处然后删除变长数组的最后一个元素。该操作的时间复杂度是 O(1)且可以保证在删除操作之后变长数组中的所有元素的下标都连续方便插入操作和获取随机元素操作。 相当于把nums的最后一个元素lastval代替val在数组中的位置同时也更新哈希表中lastval的值最后截取数组不要最后一个元素
获取随机元素操作时由于变长数组中的所有元素的下标都连续因此随机选取一个下标返回变长数组中该下标处的元素。
