Leetcode題解 Python & C#：Insert Delete GetRandom O(1) – Duplicates allowed

這題是「Insert Delete GetRandom O(1)」的進階，連運作原理都相同。

這次允許了重複出現，也就是說，一個數值的位置保存是要能容納多個的。

這時會有 list() 或是 set() 的取捨，但是由於要在 O(1) Time 的限制，就選擇 set() 來存放同val的多個位置。

其它都跟前一題差不多，前一題能解，這題就不是大問題。

Python

class RandomizedCollection:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.posMap = defaultdict(set)
        self.data = list()        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        """
        exist = val in self.posMap
        self.posMap[val].add(len(self.data))
        self.data.append(val)
        return not exist

    def remove(self, val: int) -> bool:
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        """
        exist = val in self.posMap
        if exist:
            i = self.posMap[val].pop()    
            lastVal = self.data[-1]
            self.data[i] = lastVal
            self.posMap[lastVal].add(i)             
            del self.data[-1] 
            self.posMap[lastVal].discard(len(self.data))
            if not self.posMap[val]: del self.posMap[val]
        return exist        

    def getRandom(self) -> int:
        """
        Get a random element from the collection.
        """
        return self.data[int(random.random()*len(self.data))]

C#

public class RandomizedCollection {
    private Dictionary> posMap;
    private List data;
    public Random rand;

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        posMap = new Dictionary>(); 
        data = new List();
        rand = new Random();
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public bool Insert(int val) {
        bool exist = posMap.ContainsKey(val);
        if(!(exist)){posMap[val] = new HashSet();}
        posMap[val].Add(data.Count);
        data.Add(val);
        return !(exist);
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public bool Remove(int val) {
        bool exist = posMap.ContainsKey(val);
        if(exist)
        {
            int lastNum = data[data.Count - 1];
            int i = posMap[val].First();
            data[i] = lastNum;
            posMap[val].Remove(i);            
            posMap[lastNum].Add(i);
            data.RemoveAt(data.Count - 1);
            posMap[lastNum].Remove(data.Count);  
            if(posMap[val].Count == 0){posMap.Remove(val);}
        }
        return exist;        
    }
    
    /** Get a random element from the collection. */
    public int GetRandom() {
        return data[rand.Next(0, data.Count)];
    }
}