2019 - 11 - 27 상수 시간 에 무 작위 요 소 를 삽입, 삭제, 가 져 옵 니 다.

평균 시간 복잡 도 O (1) 에서 다음 작업 을 수행 할 수 있 는 데이터 구 조 를 설계 합 니 다.
insert (val): 요소 val 이 존재 하지 않 을 때 집합 에 이 항목 을 삽입 합 니 다.remove (val): 요소 val 이 존재 할 때 집합 에서 이 항목 을 제거 합 니 다.getRandom: 기 존 집합 중 하 나 를 무 작위 로 되 돌려 줍 니 다.모든 요 소 는 같은 확률 로 되 돌아 와 야 한다.예시:

//          。
RandomizedSet randomSet = new RandomizedSet();

//        1 。   true    1       。
randomSet.insert(1);

//    false ，         2 。
randomSet.remove(2);

//        2 。   true 。       [1,2] 。
randomSet.insert(2);

// getRandom       1   2 。
randomSet.getRandom();

//        1 ，   true 。       [2] 。
randomSet.remove(1);

// 2      ，     false 。
randomSet.insert(2);

//    2          ，getRandom      2 。
randomSet.getRandom();

주의 하 다.
1. c++ 의 유형 체 에서 방법 이외 의 구역 은 초기 화 를 허용 하지 않 습 니 다. 간단 한 유형 은 가능 하지만 구조 함수 가 있 는 복잡 한 대상 은 안 됩 니 다. 예 를 들 어 int 대상!공간 을 수 동 으로 호출 reverse 할 수도 있다.

class C{
private:
    vector v(9);  //error,expected identifier before numeric constant
public:
void test(){}
};

2. C++ 무 작위 수의 함수 가 발생 하고 srand 와 rand.프로그램 이 연속 적 으로 무 작위 수 를 호출 해 야 할 때 시계 에 따라 무 작위 피 드 를 정의 하지 마 십시오. 그러면 프로그램 이 매우 빨리 실행 되 기 때문에 매번 설정 한 피 드 가 똑 같 아서 매번 에 모든 무 작위 수 를 생 성 할 때마다 똑 같 아서 통과 할 수 없습니다!!
보통 추천: srand((unsigned)time(NULL)); 또는 srand((unsigned)time(0));time 에 대하 여t time (0): time_t 는 장정 형 으로 정의 되 었 고 1970 년 1 월 1 일 0 시 0 분 0 초 에서 지금까지 거 친 시간, 단 위 는 로 되 돌 아 왔 다.
C++1

class RandomizedSet {
private:
    vector v; //    
    map m; //          
    int index;
    int flag;
public:
    /** Initialize your data structure here. */
    RandomizedSet() {
        v.reserve(10000); //        ，    ：AddressSanitizer: heap-buffer-overflow on address 0x602000000114 at pc 0x000000416046 bp 0x7ffd7453cd20 sp 0x7ffd7453cd18
        index = 0; //v   
        flag = 1;
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    bool insert(int val) {
        if(m.count(val)>0){
            return false;
        }else{
            if(flag == 1){
                v.push_back(val);
                flag = 0;
            }else{
                v[index] = val;
            }
            
            m.insert(make_pair(val, index++));
            return true;
        }
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    bool remove(int val) {
        if(m.count(val)>0){
            int t = v[index-1]; //      
            m[t] = m[val];
            v[m[val]] = t;
            m.erase(val);
            index--;
            return true;
        }else{
            return false;
        }
    }
    
    /** Get a random element from the set. */
    int getRandom() {
        //srand((int)time(0));  //               ，          getRandom  ，            ，    
        int num = rand()%index;
        return v[num];
    }
};

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