算法:O(1) 时间插入、删除和获取随机元素---哈希表+动态数组

这篇具有很好参考价值的文章主要介绍了算法:O(1) 时间插入、删除和获取随机元素---哈希表+动态数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法:O(1) 时间插入、删除和获取随机元素---哈希表+动态数组,算法,算法,散列表,数据结构,哈希表,数组,动态数组,变长数组


1、题目:

实现RandomizedSet 类:

  • RandomizedSet() 初始化 RandomizedSet 对象
  • bool insert(int val) 当元素 val 不存在时,向集合中插入该项,并返回 true ;否则,返回 false
  • bool remove(int val) 当元素 val 存在时,从集合中移除该项,并返回 true ;否则,返回 false
  • int getRandom() 随机返回现有集合中的一项(测试用例保证调用此方法时集合中至少存在一个元素)。每个元素应该有 相同的概率 被返回。

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


2、分析特点:

  • 题目要求:插入、删除和获取随机元素的时间复杂度都是 O(1)

  • 在遍历获取查询方面,数组可以实现 时间复杂度都是 O(1),但是插入和删除,要求判断val是否存在,导致了插入和删除会超过O(1)

  • 哈希表可以在 O(1) 的时间内完成插入和删除操作

  • 所以:哈希表+动态数组

变长数组可以在 O(1) 的时间内完成获取随机元素操作,但是由于无法在 O(1) 的时间内判断元素是否存在,因此不能在 O(1) 的时间内完成插入和删除操作。哈希表可以在 O(1) 的时间内完成插入和删除操作,但是由于无法根据下标定位到特定元素,因此不能在 O(1) 的时间内完成获取随机元素操作。为了满足插入、删除和获取随机元素操作的时间复杂度都是 O(1),需要将变长数组和哈希表结合,变长数组中存储元素,哈希表中存储每个元素在变长数组中的下标。

插入操作时,首先判断 val 是否在哈希表中,如果已经存在则返回 false,如果不存在则插入 val,操作如下:

在变长数组的末尾添加 val;
在添加 val 之前的变长数组长度为 val 所在下标 index,将 val 和下标 index 存入哈希表;
返回 true。

删除操作时,首先判断 val是否在哈希表中,如果不存在则返回 false,如果存在则删除 val,操作如下:

从哈希表中获得 val 的下标 index;
将变长数组的最后一个元素 last 移动到下标 index 处,在哈希表中将 last 的下标更新为 index;
在变长数组中删除最后一个元素,在哈希表中删除 val;
返回 true。

删除操作的重点在于将变长数组的最后一个元素移动到待删除元素的下标处,然后删除变长数组的最后一个元素。该操作的时间复杂度是 O(1),且可以保证在删除操作之后变长数组中的所有元素的下标都连续,方便插入操作和获取随机元素操作。

获取随机元素操作时,由于变长数组中的所有元素的下标都连续,因此随机选取一个下标,返回变长数组中该下标处的元素。


3、代码:

class RandomizedSet {
    List<Integer> nums;
    Map<Integer, Integer> indices;
    Random random;

    public RandomizedSet() {
        nums = new ArrayList<Integer>();
        indices = new HashMap<Integer, Integer>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (indices.containsKey(val)) {
            return false;
        }
        int index = nums.size();
        nums.add(val);
        indices.put(val, index);
        return true;
    }

    public boolean remove(int val) {
        if (!indices.containsKey(val)) {
            return false;
        }
        int index = indices.get(val);
        int last = nums.get(nums.size() - 1);
        nums.set(index, last);
        indices.put(last, index);
        nums.remove(nums.size() - 1);
        indices.remove(val);
        return true;
    }

    public int getRandom() {
        int randomIndex = random.nextInt(nums.size());
        return nums.get(randomIndex);
    }
}

4、复杂度分析:

  • 时间复杂度:初始化和各项操作的时间复杂度都是 O(1)。

    空间复杂度:O(n),其中 n 是集合中的元素个数。存储元素的数组和哈希表需要 O(n) 的空间。


5、总结:

关于O(1)的时间平均复杂度的设计都离不开哈希表
一般插入、删除、获取,数组可以实现,就选数组,简单些
可以根据题目,对两种数据结构进行组合使用,比如:数组+哈希表




如果本文对你有帮助的话记得给一乐点个赞哦,感谢!文章来源地址https://www.toymoban.com/news/detail-713714.html

到了这里,关于算法:O(1) 时间插入、删除和获取随机元素---哈希表+动态数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包