Umetanje Izbriši GetRandom O(1) Leetcode Rješenje

Izjava o problemu

Korištenje električnih romobila ističe Umetanje Delete GetRandom O(1) LeetCode Rješenje – “Insert Delete GetRandom O(1)” traži od vas da implementirate ove četiri funkcije u O(1) vremenskoj složenosti.

• umetnuti (val): Umetnite val u nasumični skup i vratiti istina ako element u početku nema u skupu. Vraća lažno kada je element već prisutan u skupu.
• ukloniti (val): Uklanja val iz randomiziranog skupa i vraća true ako je element inicijalno prisutan u skupu. Vraća lažno kada element nije prisutan u skupu.
• getRandom(): Vraća slučajni element iz trenutnog skupa elemenata. Svaki element mora imati istu vjerojatnost da bude vraćen.

Primjer:

bor

Input:  ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
        [[], [1], [2], [2], [], [1], [2], []]

Output: [null, true, false, true, 2, true, false, 2]

Objašnjenje:

• RandomizedSet randomizedSet = novi RandomizedSet();
• insert(1), umeće 1 u skup i vraća true jer je 1 uspješno umetnuto.
• remove(2), vraća false jer 2 ne postoji u skupu.
• insert(2), umeće 2 u skup i vraća true. Skup sada sadrži [1, 2].
• getRandom(), trebao bi nasumično vratiti 1 ili 2.
• remove(1), uklanja 1 iz skupa i vraća true. Set sada sadrži [2].
• insert(2), 2 je već bio u skupu pa vrati false.
• getRandom(), budući da je 2 jedini broj u skupu, getRandom() će uvijek vratiti 2.

Pristup

Ideja:

1. Glavna ideja za rješavanje ovog problema je korištenje HashSet.
2. Održavat ćemo niz za pohranjivanje elemenata sekvencijalno kada dođe do umetanja.
3. Također, HashSet se koristi za mapiranje umetnutih elemenata na njihove pozicije u nizu.
4. Za umetnuti() operacija:
   1. Ako element već postoji, nema potrebe za umetanjem, vratiti lažno inače,
   2. Umetnite element u niz i pohranite poziciju trenutnog elementa u HashSet i vratiti istina.
5. Za ukloniti() operacija:
   1. Ako element ne postoji u nizu, vratiti lažno inače,
   2. Uklonite element iz niza, zamijenite trenutni element zadnjim elementom niza i održavati indekse ova dva elementa i ukloniti posljednji element iz niza i vratiti istina.
6. Za getRandom() operaciju, koristite funkciju rand() za generirati slučajni element i izbaci nasumični element iz trenutnog skupa u O(1) vremenu.

Kodirati

Umetni Delete GetRandom O(1) Leetcode C++ Rješenje:

class RandomizedSet {
public:
    
    vector <int> elements;
    unordered_map <int, int> index;
    
    RandomizedSet() {
        index.clear();
        elements.clear();
    }
    
    bool insert(int val) {
        if(index.count(val)){
            return false;
        }
        
        index[val] = elements.size();
        
        elements.push_back(val);
        
        return true;
    }
    
    bool remove(int val) {
        if(!index.count(val)){
            return false;
        }
        
        int last = elements.back();
        
        elements.pop_back();
        elements[index[val]] = last;
        
        index[last] = index[val];
        index.erase(val);
        
        return true;
    }
    
    int getRandom() {
        int sz = elements.size();
        return elements[rand()%sz];
    }
};

Umetanje Delete GetRandom O(1) Leetcode Java rješenje:

public class RandomizedSet {
    ArrayList<Integer> nums;
    HashMap<Integer, Integer> locs;
    java.util.Random rand = new java.util.Random();
    
    public RandomizedSet() {
        nums = new ArrayList<Integer>();
        locs = new HashMap<Integer, Integer>();
    }
    
    public boolean insert(int val) {
        boolean contain = locs.containsKey(val);
        if ( contain ) return false;
        locs.put( val, nums.size());
        nums.add(val);
        return true;
    }
    
    public boolean remove(int val) {
        boolean contain = locs.containsKey(val);
        if ( ! contain ) return false;
        int loc = locs.get(val);
        if (loc < nums.size() - 1 ) {
            int lastone = nums.get(nums.size() - 1 );
            nums.set( loc , lastone );
            locs.put(lastone, loc);
        }
        locs.remove(val);
        nums.remove(nums.size() - 1);
        return true;
    }
    
    public int getRandom() {
        return nums.get( rand.nextInt(nums.size()) );
    }
}

Analiza složenosti za Insert Delete GetRandom O(1) Leetcode Rješenje

Složenost vremena

Vremenska složenost sve tri funkcije je O (1). Dobra hash funkcija omogućuje umetanje/brisanje u O(1) vremenu.

Složenost prostora

Složenost prostora gornjeg koda je NA) gdje je N = maksimalna veličina randomiziranog skupa.

Glavna pitanja za intervju