leetcode Insert Delete GetRandom O(1)

leetcode Insert Delete GetRandom O(1)

Design a data structure that supports all following operations in O(1) time.

  1. insert(val): Inserts an item val to the set if not already present.
  2. remove(val): Removes an item val from the set if present.
  3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

题目地址:leetcode Insert Delete GetRandom O(1)

题目大意: 要求实现一个数据结构,可以支持插入,删除,随机数生成。 他们的复杂度均要求O(1)

思路:用hash记录下标, 删除只需要和末尾元素调换即可

ps :无聊身边没电脑用手机1A了此题。。。还发了blog

 

本题是leetcode 380 Insert Delete GetRandom O(1)的题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Insert Delete GetRandom O(1)
本文地址:https://www.hrwhisper.me/leetcode-insert-delete-getrandom-o1/

听说长得好看的已经打赏了

Leetcode , , . permalink.

One thought on “leetcode Insert Delete GetRandom O(1)

Leave a Reply

Your email address will not be published. Required fields are marked *