ינסערט דיליט געטראַנדאָם


שוועריקייט לעוועל מיטל
אָפט געבעטן אין פעסטשטעלן אַמאַזאָן אַפּפּדינאַמיקס עפּל בלומבערג ציטאַדעל facebook גוגל מייקראָסאָפֿט נווידיאַ אָראַקל קוועראַ טוויטטער צוויי סיגמאַ יאַנדעקס זיללאָוו
מענגע פּלאַן האַש

אין ינסערט ויסמעקן GetRandom פּראָבלעם, מיר דאַרפֿן צו פּלאַן אַ דאַטן סטרוקטור וואָס שטיצט אַלע ווייַטערדיק אַפּעריישאַנז אין דורכשניטלעך אָ (1) צייט.

  1. insert (val): ינסערט אַ נומער פון וואַל צו די סכום אויב עס איז נישט פאָרשטעלן.
  2. אַראָפּנעמען (וואַל): רימוווז אַ נומער וואַל פון די שטעלן אויב עס איז פאָרשטעלן.
  3. getRandom: רעטורנס אַ טראַפ עלעמענט פֿון דעם קראַנט שטעלן פון עלעמענטן. יעדער עלעמענט מוזן האָבן די זעלביקער מאַשמאָעס פון ווערן אומגעקערט.

ווייַל די קשיא דאַרף ינסערשאַן און דילישאַן אָפּעראַציע אין אָ (1), דעריבער מיר דאַרפֿן אַ מאַפּע. אָבער פֿאַר getRandom () אופֿן, מיר דאַרפֿן אַן אינדעקס-באזירט דאַטן סטרוקטור ווי אַ מענגע, אַזוי מיר קענען ראַנדאַמלי קלייַבן קיין אינדעקס עלעמענט צו צוריקקומען.

דעריבער, צו באַקומען אַלע די דריי פאַנגקשאַנאַליטי, מיר קענען נוצן ביידע מאַפּע און מענגע צוזאַמען. זאל ס זען ווי

וויכטיק פונקטן

  1. ינסערשאַן אין די מענגע איז אָ (1) אויב געטאן אין די צוריק.
  2. דילישאַן אין די מענגע איז אָ (1) אויב דער עלעמענט איז אַוועקגענומען פון די צוריק.

דאַטן סטראַקטשערז געוויינט

מאַפּע M (צו קראָם ווערט, אינדעקס פּאָר)

וועקטאָר V צו קראָם איצטיקע עלעמענטן

אַלגערידאַם פֿאַר ינסערשאַן

  1. קאָנטראָלירן אויב די געגעבן עלעמענט איז פאָרשטעלן אין די מאַפּע:
    • אויב עס איז פאָרשטעלן, צוריקקומען פאַלש
    • אלזא:
      • אַרייַן די געגעבן עלעמענט אין די סוף פון וועקטאָר V.
      • אַרייַן געגעבן עלעמענט און עס איז אַן אינדעקס צו מאַפּע M
      • צוריקקומען אמת

אַלגערידאַם פֿאַר דילישאַן

  1. קאָנטראָלירן אויב די געגעבן עלעמענט איז פאָרשטעלן אין די מאַפּע:
    • אויב פאָרשטעלן, דאַן:
      • ויסבייַטן די וואַלועס געגעבן עלעמענט און לעצטע עלעמענט אין די וועקטאָר (אינדעקס קענען זיין געפֿונען ניצן מאַפּע M
      • דערהייַנטיקן די מאַפּע ווי M [last_element] = M [given_element]
      • ויסמעקן די לעצטע עלעמענט פון די וועקטאָר.
      • ויסמעקן די געגעבן עלעמענט פֿון דער מאַפּע
      • צוריקקומען אמת.
    • אַנדערש, צוריקקומען פאַלש.

אַלגערידאַם פֿאַר getRandom

  1. סעלעקטירן קיין טראַפ - אינדעקס i
  2. n די קייט פון 0 צו די גרייס פון דעם וועקטאָר.
  3. ווייַזן עלעמענט פאָרשטעלן אין דעם אינדעקס אין וועקטאָר V.

ימפּלעמענטאַטיאָן פֿאַר ינסערט ויסמעקן 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

רעפֿערענצן