leetcode Insert Delete GetRandom O(1) – Duplicates allowed

leetcode Insert Delete GetRandom O(1) – Duplicates allowed

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

Note: Duplicate elements are allowed.

  1. insert(val): Inserts an item val to the collection.
  2. remove(val): Removes an item val from the collection if present.
  3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

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

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

思路:其实和上一题  leetcode Insert Delete GetRandom O(1) 差不多,只不过这题允许重复,把字典里换成一个哈希表的set即可(注意,不可以是list)

比如如下的数据,list无法保证顺序!特别感谢@guanglightman 指出

 

C++

 

Python

 

 

本题是leetcode 381 Insert Delete GetRandom O(1) – Duplicates allowed 的题解

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

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

您的支持将鼓励我继续创作!

Leetcode , , , . permalink.

13 thoughts on “leetcode Insert Delete GetRandom O(1) – Duplicates allowed

  1. SET 的REMOVE 明显不是 O(1)吧

    self.index[last].remove(len(self.output))
    这句话本质上和用个LIST来存 没什么区别

  2. The above algorithm maybe not safe (and also I doubt it’s correctness). I think everything inside the list index[val] should be maintained in ordered.

    A simple example:
    start from 3 4 5 6 1 2 1 2
    and then remove 3 4 5 6 2 2
    in the last step(remove 2), the code has accessed outbound memory.

    • You are right. Thanks for pointing it out.
      My solution is not correct because it is not maintain the index order.
      If we keep the index order, use a heap or AVL tree or binary search or like Insertion sort, it will be right, but it is not O(1).
      I doubt the problem has not O(1) solution.

      • A randomized algorithm is listed below, You may find some explanation in comment part inside the code. Some issues may also remained.

        Best,
        Guang

Leave a Reply

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