380. Insert Delete GetRandom O(1)

 문제: leetcode.com/problems/insert-delete-getrandom-o1/

Insert Delete GetRandom O(1) - LeetCode

 

class RandomizedSet {
public:
    /** Initialize your data structure here. */
    unordered_map<int, int> h;
    list<int> lst;
    RandomizedSet() {
        
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(h.find(val) != h.end()){
            return false;
        }
        lst.push_back(val);
        h[val] = lst.size() - 1;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(h.find(val) == h.end()){
            return false;
        }
        int idx = h[val];
        int e = lst.back();
        auto it = lst.begin();
        advance(it, idx);
        int c = *it;
        *it = e;
        h[e] = idx;
        h.erase(c); // time complexity? -> average O(1)
        lst.pop_back();
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        if(lst.size() == 1) return lst.front();
        int len = lst.size();
        auto it = lst.cbegin();
        
        int random =  rand() % (lst.size());
        advance(it, random);
        return *it;
    }
};

/**
 * 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();
 */

 List와 unordered_map을 사용해서 average O(1)만에 삽입, 삭제, random access를 하는 문제다.   

 

 

Table & List example

 테이블에 IDX를 key로주고 실제 값을 value에 저장한다.  이 INDEX가 Table에 고정되있으므로 List에서 삭제를 할 때 기존의 INDEX를 유지해주면서 삭제해야한다.   lst.erase(lst.begin()) 이런식으로 삭제하면 기존의 INDEX가 다 깨져서 일관성이 유지되지 않는다.  INDEX를 유지하는 방법은 맨 마지막에 있는 노드 값을 삭제할 대상 노드의 값과 swap하고 Table에서 해당 부분만 갱신해준다음 pop_back을 해준다.  이렇게하면 전체 노드들의 INDEX는 유지된다.

 

 

 

getRandom 결과

 

 상대적으로 속도가 안나온다... 놓친게 있나?   / 2021-02-11 아침

 iterator를 advance로 포지션 맞춰줄때 시간이 드는거같은데 random access iterator?

출처: www.cplusplus.com/reference/iterator/advance/

 

 이런 개념이면 인덱싱이 가능한 vector로 하는게 더 유리하다.

 

class RandomizedSet {
public:
    /** Initialize your data structure here. */
    unordered_map<int, int> h;
    vector<int> lst;
    RandomizedSet() {
        
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(h.find(val) != h.end()){
            return false;
        }
        lst.push_back(val);
        h[val] = lst.size() - 1;
        return true;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(h.find(val) == h.end()){
            return false;
        }
        int idx = h[val];
        int e = lst.back();
        int c = lst[idx];
        lst[idx] = e;
        h[e] = idx;
        h.erase(c); // time complexity? -> average O(1)
        lst.pop_back();
        return true;
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        int r =  rand() % (lst.size());
        return lst[r];
    }
};

/**
 * 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();
 */

 vector로 재작성했다.  불필요한 작업들이 줄어들어 시간이 100% 가까이 나온다.

 

 

 // 2021-02-11 11:48