LeetCode：挿入削除getrandom o1 C＃

Question

https://leetcode.com/problems/insert-delete-getrandom-o1/

パフォーマンスについてコメントしてください

RandomizedSetクラスを実装します。

bool insert（int val）存在しない場合、アイテムvalをセットに挿入します。アイテムが存在しない場合はtrueを返し、そうでない場合はfalseを返します。bool remove（int val）存在する場合、セットからアイテムvalを削除します。アイテムが存在する場合はtrueを返し、存在しない場合はfalseを返します。int getRandom（）現在の要素のセットからランダムな要素を返します（このメソッドが呼び出されたときに少なくとも1つの要素が存在することが保証されています）。各要素は、返される確率が同じである必要があります。フォローアップ：各関数が平均O（1）時間で機能するように、クラスの関数を実装できますか？

例1：

入力["RandomizedSet"、 "insert"、 "remove"、 "insert"、 "getRandom"、 "remove"、 "insert"、 "getRandom"] [[]、[1]、[2]、[2]、 []、[1]、[2]、[]]出力[null、true、false、true、2、true、false、2]

説明RandomizedSetrandomizedSet = new RandomizedSet（）; randomizedSet.insert（1）; //セットに1を挿入します。1が正常に挿入されたため、trueを返します。randomizedSet.remove（2）; // 2がセットに存在しないため、falseを返します。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を返します。

制約：

\$-2^{31} <= val <= 2^{31} - 1\$。せいぜい\$10^5\$挿入、削除、およびgetRandomの呼び出しが行われます。getRandomが呼び出されると、データ構造に少なくとも1つの要素があります。

public class RandomizedSet {
    
     private HashSet<int> _set;
        /** Initialize your data structure here. */
        public RandomizedSet()
        {
            _set = new HashSet<int>();
        }

        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public bool Insert(int val)
        {
            if (_set.Contains(val))
            {
                return false;
            }
            _set.Add(val);
            return true;
        }

        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public bool Remove(int val)
        {
            if (_set.Contains(val))
            {
                _set.Remove(val);
                return true;
            }
            return false;
        }

        /** Get a random element from the set. */
        public int GetRandom()
        {
            Random rand = new Random();
            int key = rand.Next(_set.Count);
            return _set.ElementAt(key);
        }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * bool param_1 = obj.Insert(val);
 * bool param_2 = obj.Remove(val);
 * int param_3 = obj.GetRandom();
 */

Answer 1

• HashSet<int>それを作るので、変更されませんreadonly。
• の呼び出しのContains()前に呼び出す代わりにAdd()、これがと評価された場合、値がすでににある場合にメソッドが戻るという理由falseだけで単純化できます。参照return _set.Add(val);Add()falseHashSet
• 呼び出すContains()前に呼び出す代わりに、アイテムがにない場合に返されるという理由Remove()だけで簡略化することもできます。参照return _set.Remove(val);Remove()falseHashSet
• .NET Frameworkで作成されたのは現在のタイムスタンプに基づいているGetRandom()ため、短い順序で繰り返し呼び出すと、同じ要素になる可能性があります。使用するクラスレベルを作成することをお勧めします。SeedRandomRandom

まとめると

public class RandomizedSet {
    
    private readonly HashSet<int> _set;
    /** Initialize your data structure here. */
    public RandomizedSet()
    {
        _set = new HashSet<int>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public bool Insert(int val)
    {
        return _set.Add(val);
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public bool Remove(int val)
    {
        return _set.Remove(val);
    }

    private readonly Random rand = new Random();
    /** Get a random element from the set. */
    public int GetRandom()
    {
        int key = rand.Next(_set.Count);
        return _set.ElementAt(key);
    }
}

Answer 2

GetRandom() 複雑

HashSet<T>インデックスによるルックアップをサポートしていないためElementAt、要求された要素に到達するまで繰り返す必要があります。それには、O（1）ではなくO（n）ステップが必要です。