हटाएं GetRandom


कठिनाई स्तर मध्यम
में अक्सर पूछा वाणी वीरांगना ऐप डायनामिक्स सेब ब्लूमबर्ग गढ़ Facebook गूगल माइक्रोसॉफ्ट Nvidia ओरेकल क्वेरा Twitter दो सिग्मा Yandex Zillow
ऐरे डिज़ाइन हैश

इंसर्ट डिलीट गेटग्रैंडम प्रॉब्लम में हमें एक डेटा स्ट्रक्चर तैयार करना होगा जो निम्नलिखित सभी ऑपरेशनों को सपोर्ट करता है औसत ओ (१) समय।

  1. इन्सर्ट (वैल): यदि पहले से मौजूद नहीं है तो सेट के लिए एक आइटम वैल सम्मिलित करता है।
  2. remove (val): यदि मौजूद हो तो सेट से कोई आइटम वैल निकालता है।
  3. getRandom: तत्वों के वर्तमान सेट से एक यादृच्छिक तत्व देता है। प्रत्येक तत्व में होना चाहिए समान संभावना लौटाया जा रहा है।

चूंकि प्रश्न को ओ (1) में सम्मिलन और विलोपन ऑपरेशन की आवश्यकता है, इसलिए हमें एक मानचित्र की आवश्यकता है। लेकिन getRandom () विधि के लिए, हमें एक सरणी की तरह एक सूचकांक आधारित डेटा संरचना की आवश्यकता होती है ताकि हम बेतरतीब ढंग से लौटने के लिए किसी भी सूचकांक तत्व को चुन सकें।

इसलिए सभी तीन कार्यशीलता को प्राप्त करने के लिए, हम मानचित्र और सरणी दोनों का एक साथ उपयोग कर सकते हैं। आइए देखें कैसे

महत्वपूर्ण बिंदु

  1. में सम्मिलन सरणी O (1) है अगर पीछे की तरफ।
  2. सरणी में विलोपन O (1) है यदि तत्व को पीछे से हटा दिया जाता है।

डेटा संरचनाओं का इस्तेमाल किया

मैप एम (मूल्य, इंडेक्स पेयर स्टोर करने के लिए)

वर्तमान तत्वों को संग्रहीत करने के लिए वेक्टर वी

सम्मिलन के लिए एल्गोरिदम

  1. जाँच करें कि क्या दिए गए तत्व नक्शे में मौजूद हैं:
    • अगर मौजूद है, तो झूठे लौटाओ
    • अन्य:
      • वेक्टर V के अंत में दिए गए तत्व को डालें
      • दिए गए तत्व डालें और यह M को मैप करने के लिए एक इंडेक्स है
      • सच लौटा दो

विलोपन के लिए एल्गोरिदम

  1. जाँच करें कि क्या दिए गए तत्व नक्शे में मौजूद हैं:
    • यदि मौजूद है, तो:
      • वेक्टर में दिए गए तत्व और अंतिम तत्व को स्वैप करें (इंडेक्स मैप M का उपयोग करके पाया जा सकता है)
      • मानचित्र को M [last_element] = M [दिए गए_हेलमेंट] के रूप में अपडेट करें
      • वेक्टर के अंतिम तत्व को हटा दें।
      • दिए गए तत्व को मानचित्र से मिटाएँ
      • सच लौटा दो।
    • और, झूठे लौटे।

GetRandom के लिए एल्गोरिथम

  1. किसी भी यादृच्छिक सूचकांक का चयन करें i
  2. n वेक्टर की साइज में 0 की रेंज।
  3. वेक्टर V में उस इंडेक्स पर मौजूद रिटर्न एलिमेंट।

इंसर्ट डिलीट गेटट्रैंड के लिए कार्यान्वयन

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

सम्मिलित करें हटाएँ के लिए जावा कार्यक्रम

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

संदर्भ