LeetCode: แทรกลบ getrandom o1 C #

Question

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

โปรดแสดงความคิดเห็นเกี่ยวกับประสิทธิภาพ

ใช้คลาส RandomizedSet:

bool insert (int val) ใส่ item val ลงในชุดหากไม่มีอยู่ ส่งคืนค่าจริงหากไม่มีรายการอยู่มิฉะนั้นจะเป็นเท็จ bool remove (int val) ลบ item val ออกจากชุดถ้ามี ส่งคืนค่าจริงหากมีรายการอยู่มิฉะนั้นจะเป็นเท็จ int getRandom () ส่งคืนองค์ประกอบแบบสุ่มจากชุดองค์ประกอบปัจจุบัน (รับประกันว่ามีอย่างน้อยหนึ่งองค์ประกอบเมื่อเรียกวิธีนี้) แต่ละองค์ประกอบต้องมีความน่าจะเป็นที่จะถูกส่งกลับไม่เท่ากัน ติดตามผล: คุณสามารถใช้ฟังก์ชันของคลาสโดยแต่ละฟังก์ชันทำงานโดยเฉลี่ย O (1) ครั้งได้หรือไม่?

ตัวอย่างที่ 1:

อินพุต ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] เอาต์พุต [null, true, false, true, 2, true, false, 2]

คำอธิบาย RandomizedSet randomizedSet = new RandomizedSet (); randomizedSet.insert (1); // แทรก 1 ในชุด ส่งคืนค่าจริงเมื่อใส่ 1 สำเร็จ randomizedSet.remove (2); // ส่งคืนค่าเท็จเนื่องจาก 2 ไม่มีอยู่ในชุด randomizedSet.insert (2); // แทรก 2 ลงในเซตส่งคืนค่าจริง ตอนนี้มี [1,2] randomizedSet.getRandom (); // getRandom () ควรส่งคืน 1 หรือ 2 แบบสุ่ม randomizedSet.remove (1); // ลบ 1 ออกจากชุดส่งคืนค่าจริง ตอนนี้มี [2] randomizedSet.insert (2); // 2 อยู่ในชุดแล้วดังนั้นให้คืนค่าเท็จ randomizedSet.getRandom (); // เนื่องจาก 2 เป็นตัวเลขเดียวในชุด getRandom () จะส่งคืน 2 เสมอ

ข้อ จำกัด :

\$-2^{31} <= val <= 2^{31} - 1\$. มากที่สุด\$10^5\$จะทำการโทรเพื่อแทรกลบและ getRandom จะมีอย่างน้อยหนึ่งองค์ประกอบในโครงสร้างข้อมูลเมื่อ getRandom ถูกเรียกใช้

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()วิธีการส่งคืนfalseหากค่าทั้งหมดอยู่ในHashSet. ข้อมูลอ้างอิง
• แทนที่จะโทรContains()ก่อนที่จะโทรRemove()สามารถทำให้ง่ายขึ้นได้เช่นกันreturn _set.Remove(val);เพราะRemove()จะส่งคืนfalseหากรายการไม่อยู่ในไฟล์HashSet. ข้อมูลอ้างอิง
• การเรียกGetRandom()ลำดับสั้น ๆ ซ้ำ ๆ กันอาจส่งผลให้เกิดองค์ประกอบเดียวกันเนื่องจากเฟรมเวิร์กที่Seedสร้างขึ้นRandomใน. NET นั้นขึ้นอยู่กับการประทับเวลาปัจจุบัน มันจะดีกว่าที่จะสร้างระดับระดับRandomที่จะใช้

การสรุปนำไปสู่

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 (n) ไม่ใช่ O (1)