Տեղադրեք Deleteնջել GetRandom- ը


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Հաստատել Amazon AppDynamics խնձոր Bloomberg Միջնաբերդ facebook Google Microsoft Nvidia Պատգամախոս Կուերա ծլվլոց Երկու սիգմա Yandex Zillow
Դասավորություն Դիզայն Խանգարել

Տեղադրեք Deleteնջել GetRandom խնդիրը, մենք պետք է նախագծենք տվյալների կառուցվածք, որն աջակցում է հետևյալ բոլոր գործողությունները միջին O (1) ժամանակ:

  1. ներդիր (փական). իրը տեղադրում է հավաքածուի մեջ, եթե այն արդեն առկա չէ:
  2. remove (val). առկայության դեպքում ջնջում է իրը:
  3. getRandom. Վերադարձնում է պատահական տարր տարրերի ընթացիկ շարքից: Յուրաքանչյուր տարր պետք է ունենա այն նույն հավանականությունը վերադարձվելու մասին:

Քանի որ հարցը O (1) –ում տեղադրման և ջնջման գործողության կարիք ունի, ուստի մեզ քարտեզ է պետք: Բայց getRandom () մեթոդի համար մեզ անհրաժեշտ է զանգվածի նման ինդեքսի վրա հիմնված տվյալների կառուցվածք, որպեսզի վերադարձման համար կարողանանք պատահականորեն ընտրել ցանկացած ինդեքսի տարր:

Այսպիսով, բոլոր երեք գործառույթները ստանալու համար մենք կարող ենք միասին օգտագործել և՛ քարտեզը, և՛ զանգվածը: Տեսնենք ինչպես

Կարևոր կետեր

  1. Տեղադրում է դասավորություն O է (1), եթե արված է հետևում:
  2. Rayանգվածի ջնջումը O (1) է, եթե տարրը հանվում է հետևից:

Օգտագործված տվյալների կառուցվածքներ

Քարտեզ M (արժեքը պահելու, ինդեքսային զույգ)

Վեկտոր V ՝ ներկա առկա տարրերը պահելու համար

Տեղադրման ալգորիթմ

  1. Ստուգեք, արդյոք տվյալ տարրը քարտեզում առկա է.
    • Եթե ​​առկա է, ապա կեղծ վերադարձիր
    • Ուրիշ:
      • Տեղադրեք տրված տարրը V վեկտորի վերջում
      • Տեղադրեք տրված տարրը և դա ցուցանիշ է M- ի քարտեզագրման համար
      • Վերադարձիր ճշմարիտ

Gorնջման ալգորիթմ

  1. Ստուգեք, արդյոք տվյալ տարրը քարտեզում առկա է.
    • Եթե ​​առկա է, ապա.
      • Վեկտորում փոխեք տրված տարրի և վերջին տարրի արժեքները (ինդեքսը կարելի է գտնել M քարտեզի միջոցով)
      • Քարտեզը թարմացնել որպես M [last_element] = M [տրված_էլեմենտ]
      • Deleteնջեք վեկտորի վերջին տարրը:
      • Elementնջել տրված տարրը քարտեզից
      • Վերադարձիր ճշմարիտ:
    • Ուրիշ, կեղծ վերադարձիր:

GetRandom- ի ալգորիթմ

  1. Ընտրեք ցանկացած պատահական ցուցիչ i
  2. n վեկտորի չափը 0-ից:
  3. Վեկտորի մեջ այդ ինդեքսում առկա վերադարձի տարրը:

Տեղադրեք Deleteնջել GetRandom- ի տեղադրումը

C ++ ծրագիրը տեղադրելու համար ջնջել GetRandom- ը

#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

Սայլակ