GetRandom 삭제 삽입

Insert Delete GetRandom 문제에서 다음 작업을 모두 지원하는 데이터 구조를 설계해야합니다. 평균 O (1) 시간.

1. insert (val) : 아직 존재하지 않는 경우 항목 val을 세트에 삽입합니다.
2. remove (val) :있는 경우 세트에서 항목 val을 제거합니다.
3. getRandom : 현재 요소 집합에서 임의의 요소를 반환합니다. 각 요소에는 같은 확률 반환의.

질문은 O (1)에서 삽입 및 삭제 작업이 필요하므로지도가 필요합니다. 그러나 getRandom () 메서드의 경우 반환 할 인덱스 요소를 임의로 선택할 수 있도록 배열과 같은 인덱스 기반 데이터 구조가 필요합니다.

따라서 세 가지 기능을 모두 얻으려면 맵과 배열을 함께 사용할 수 있습니다. 방법을 보자

중요한 점

1. 삽입 정렬 뒤에서하면 O (1)입니다.
2. 요소가 뒤에서 제거되면 배열의 삭제는 O (1)입니다.

사용 된 데이터 구조

M (저장 값, 인덱스 쌍) 매핑

현재 요소를 저장할 벡터 V

삽입 알고리즘

1. 지정된 요소가지도에 있는지 확인합니다.
   • 있으면 false를 반환합니다.
   • 그밖에:
     • 벡터 V의 끝에 주어진 요소를 삽입합니다.
     • 주어진 요소를 삽입하면 M을 매핑하는 인덱스입니다.
     • 참 반환

삭제 알고리즘

1. 지정된 요소가지도에 있는지 확인합니다.
   • 있는 경우 :
     • 벡터에서 주어진 요소와 마지막 요소의 값을 바꿉니다 (지수는 맵 M을 사용하여 찾을 수 있음).
     • 맵을 M [last_element] = M [given_element]로 업데이트합니다.
     • 벡터의 마지막 요소를 삭제합니다.
     • 지도에서 주어진 요소를 지 웁니다.
     • true를 반환합니다.
   • 그렇지 않으면 false를 반환합니다.

getRandom에 대한 알고리즘

1. 임의의 인덱스 선택 i
2. n 0에서 벡터 크기까지의 범위.
3. 벡터 V의 해당 인덱스에있는 요소를 반환합니다.

삽입 삭제 GetRandom 구현

삽입 삭제 GetRandom을위한 C ++ 프로그램

#include<bits/stdc++.h>
using namespace std;

class RandomizedSet {
public:
    vector<int> v;
    map<int,int> m;
    RandomizedSet() {
    }
    
    //function for insertion of given value
    bool insert(int val) {
        if(m.find(val)==m.end()){
            v.push_back(val);
            m.insert({val,v.size()-1});
            return true;
        }
        
        return false;
    }
    
    //function for removal of given value
    bool remove(int val) {
        if(m.find(val)!=m.end()){
            int last = v.back();
            m[last]=m[val];
            v[m[val]]=last;
            v.pop_back();
            m.erase(val);
            return true;
        }
        return false;
    }
    
    //function to get a random element 
    int getRandom() {
        int ran = rand()%v.size();
        return v[ran];
    }
};

int main()
{
    RandomizedSet* r = new RandomizedSet();
    r->insert(4);
    r->insert(5);
    cout<<r->getRandom()<<" ";
    r->remove(5);
    cout<<r->getRandom()<<" ";
    return 0;
}

5 4

삽입 삭제 GetRandom을위한 JAVA 프로그램

import java.util.*;
public class Main
{
    public static class RandomizedSet {
    
        HashMap<Integer, Integer> m;
        List<Integer> v;
        
        //constructor
        public RandomizedSet() {
            m = new HashMap<>();
            v = new ArrayList<>();
        }
        
        //function for insertion of given value
        public boolean insert(int val) {
            if(m.containsKey(val)) 
                return false;
            v.add(val);
            m.put(val,v.size()-1);
            return true;
        }
        
        //function for removal of given value
        public boolean remove(int val) {
            if(m.containsKey(val)){
                int last = v.get(v.size()-1);
                m.put(last,m.get(val));
                v.set(m.get(val),last);
                v.remove(v.size()-1);
                m.remove(val);
                return true;
            }
            return false;
        }
        
        //function to get a random element 
        public int getRandom() {
            int ran = (int)(Math.random()%v.size());
            return v.get(ran);
        }
    }
  public static void main(String[] args) {
      RandomizedSet obj = new RandomizedSet();
        obj.insert(6);
        obj.insert(5);
        obj.insert(3);
        System.out.print(obj.getRandom()+" ");
        obj.remove(5);
        System.out.print(obj.getRandom()+" ");
        System.out.print(obj.getRandom()+" ");
  }
}

6 6 6

참조