Delete GetRandom енгізу  


Күрделілік дәрежесі орта
Жиі кіреді Бекітіңіз Amazon AppDynamics алма Bloomberg Цитадель Facebook Google Microsoft NVIDIA Oracle Quera Twitter Екі Sigma Яндекс Zillow
Array жобалау Hash

Insert Delete GetRandom мәселесінде келесі барлық әрекеттерді қолдайтын мәліметтер құрылымын жобалау керек орташа O (1) уақыт.

  1. insert (val): егер ол жоқ болса, жиынтыққа val элементін енгізеді.
  2. алып тастау (val): егер бар болса, элементті жиынтықтан алып тастайды.
  3. getRandom: ағымдағы элементтер жиынтығынан кездейсоқ элементті қайтарады. Әрбір элементте болуы керек бірдей ықтималдық қайтару туралы.

Сұраққа O (1) енгізу және жою әрекеті қажет болғандықтан, бізге карта керек. Бірақ getRandom () әдісі үшін біз кез келген индекс элементін кездейсоқ түрде таңдай алатындай етіп, массив сияқты индекске негізделген мәліметтер құрылымына мұқтажбыз.

Осылайша, барлық үш функцияны алу үшін біз картаны да, массивті де бірге қолдана аламыз. Қалай екенін көрейік

Маңызды сәттер  

  1. Ішіне енгізу массив артында жасалса, O (1) болып табылады.
  2. Массивтегі жою O (1), егер элемент артқы жағынан алынып тасталса.

Қолданылатын мәліметтер құрылымы  

M картасы (мәнді сақтау үшін, индекс жұбы)

Қазіргі элементтерді сақтау үшін V векторы

Кірістіру алгоритмі  

  1. Берілген элементтің картада бар-жоғын тексеріңіз:
    • Егер бар болса, өтірік мәнін қайтарыңыз
    • Басқа:
      • Берілген элементті V векторының соңына салыңыз
      • Берілген элементті енгізіңіз және ол M картасын бейнелейтін индекс
      • Ақиқатқа оралу

Өшіру алгоритмі  

  1. Берілген элементтің картада бар-жоғын тексеріңіз:
    • Егер бар болса, онда:
      • Берілген және вектордағы соңғы элементтің мәндерін ауыстырыңыз (индекс M картасының көмегімен табылуы мүмкін)
      • Картаны M [last_element] = M [given_element] етіп жаңартыңыз
      • Вектордың соңғы элементін жойыңыз.
      • Берілген элементті картадан өшіріңіз
      • Ақиқатқа оралу
    • Басқа, өтірік қайтарыңыз.
Сондай-ақ, қараңыз
Ең ұзын палиндромдық салдар

GetRandom алгоритмі  

  1. Кез келген кездейсоқ индексті таңдаңыз i
  2. n вектордың өлшеміне дейінгі 0 диапазоны.
  3. V векторында осы индексте болатын қайтару элементі.

Insert Delete GetRandom бағдарламасын іске асыру  

Insert Delete 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

Кіру үшін JAVA бағдарламасы GetRandom жою

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

Әдебиеттер тізімі