GetRandom-u silin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Təsdiq edin Amazon AppDynamics alma Bloomberg Citadel Facebook google microsoft Nvidia Kahin istədi cuqquldamaq İki Sigma Yandex Zillow
Geyim Layihə SükutBaxılıb 29

Insert Delete GetRandom problemində aşağıdakı bütün əməliyyatları dəstəkləyən bir məlumat quruluşu hazırlamalıyıq orta O (1) dəfə.

  1. insert (val): Val indiki halda olmadıqda dəstə əlavə edir.
  2. çıxar (val): Varsa bir element valı dəstdən çıxarar.
  3. getRandom: Cari elementlər qrupundan təsadüfi bir element qaytarır. Hər bir elementdə olmalıdır eyni ehtimal qaytarılması.

Sualın O (1) daxil etmə və silmə əməliyyatına ehtiyacı olduğundan, bir xəritəyə ehtiyacımız var. Ancaq getRandom () metodu üçün geri dönmək üçün istənilən indeks elementini təsadüfi seçə bilmək üçün bir sıra kimi indeks əsaslı bir məlumat quruluşuna ehtiyacımız var.

Beləliklə, bütün üç funksiyanı əldə etmək üçün həm xəritəni, həm də massivi birlikdə istifadə edə bilərik. Gəlin görək necə

Vacib məqamlar

  1. İçərisinə daxiletmə array arxa tərəfdə edilərsə O (1) olur.
  2. Element arxadan çıxarılsa, massivdəki silinmə O (1) olur.

İstifadə olunan məlumat strukturları

Xəritə M (dəyər, indeks cütü saxlamaq üçün)

Mövcud elementləri saxlamaq üçün V Vektor

Yerləşdirmə üçün alqoritm

  1. Verilən elementin xəritədə olub olmadığını yoxlayın:
    • Mövcudsa, saxta qayıdın
    • Başqa:
      • Verilən elementi V vektorunun sonuna daxil edin
      • Verilmiş elementi daxil edin və M xəritəsini göstərmək üçün bir göstəricidir
      • Doğru qayıdın

Silinmə alqoritmi

  1. Verilən elementin xəritədə olub olmadığını yoxlayın:
    • Varsa, deməli:
      • Vektordakı elementi və son elementi dəyişdirin (indeks M xəritəsi istifadə edərək tapıla bilər)
      • Xəritəni M [last_element] = M [given_element] olaraq yeniləyin
      • Vektorun son elementini silin.
      • Verilən elementi xəritədən silin
      • Doğru qayıdın.
    • Başqa, yalan qayıt.

GetRandom üçün alqoritm

  1. İstənilən təsadüfi indeks seçin i
  2. n vektorun ölçüsünə qədər 0 aralığı.
  3. V vektorunda bu indeksdə olan elementi qaytarın.

Insert Delete GetRandom üçün tətbiqetmə

Taxmaq üçün C ++ Proqramı GetRandom Sil

#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

Taxmaq üçün JAVA Proqramı GetRandom Silin

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

References

Translate »