Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में ब्लैकलिस्ट के साथ यादृच्छिक चयन (Random Pick with Blacklist)


मान लीजिए हमारे पास एक ब्लैकलिस्ट B है। यह रेंज [0, N) से अद्वितीय पूर्णांकों को रखती है, हमें एक फंक्शन परिभाषित करना है जो रेंज [0, N) से एक समान यादृच्छिक पूर्णांक वापस करे जो B में न हो। हम इस फंक्शन को random() फंक्शन कॉल को कम करके अधिक अनुकूलित बनाने का प्रयास करेंगे। मान लीजिए इनपुट ऐरे इस प्रकार है -

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे -

एक मैप परिभाषित करें

  • हम N और ऐरे v के साथ आरंभ करेंगे।
  • i := 0 से प्रारंभ करें, जब i < v का आकार, i बढ़ाते हुए, करें -
    • यदि v[i] < N, तो:, m[v[i]] := -1
  • M := N - m का आकार
  • n := v का आकार
  • i := 0 से प्रारंभ करें, जब i < v का आकार, i बढ़ाते हुए, करें -
    • यदि v[i] < M, तो -
      • N को 1 से घटाएं
      • जब N, m में है, करें -
        • N को 1 से घटाएं
      • m[v[i]] := N
  • एक फंक्शन pick() परिभाषित करें
  • x := यादृच्छिक संख्या mod M
  • वापस करें (यदि x, m में मौजूद है, तो m[x], अन्यथा x)

बेहतर समझ के लिए निम्न कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h> using namespace std; class Solution { public:    int M;    map <int,int> m;    Solution(int N, vector<int>& v) {       for(int i = 0; i < v.size(); i++){          if(v[i] < N) m[v[i]] = -1;       }       M = N - (int)(m.size());       int n = v.size();       for(int i = 0; i < v.size(); i++){          if(v[i] < M){             while(m.count(--N));             m[v[i]] = N;          }       }    }    int pick() {       int x = rand() % M;       return m.count(x)? m[x] : x;    } }; main(){    vector<int> v = {2};    Solution ob(4,v);    cout << (ob.pick()) << endl;    cout << (ob.pick()) << endl;    cout << (ob.pick()) << endl; }

इनपुट

Give N = 4 and array [2]

आउटपुट

1 1 0

  1. C++ में रैंडम पॉइंटर के साथ लिस्ट कॉपी करें C++ में रैंडम पॉइंटर के साथ लिस्ट कॉपी करें

    लिंक्ड लिस्ट एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड के दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरा ब्लॉक अगले फील्ड का पता रखता है। मान लीजिए हमारे पास एक लिंक्ड लिस्ट है जैसे कि प्रत्येक नोड में एक रैंडम पॉइंटर होता है जो लिस्ट में अन्य नोड्स की ओर इंगित करता है।

  1. C++ में उदाहरण के साथ एक्सप्रेशन ट्री C++ में उदाहरण के साथ एक्सप्रेशन ट्री

    एक एक्सप्रेशन ट्री एक विशेष प्रकार का बाइनरी ट्री है जिसमें ट्री का प्रत्येक नोड या तो एक ऑपरेटर या ऑपरेंड से बना होता है। लीफ नोड्स ट्री के एक ऑपरेंड को दर्शाते हैं। नॉन-लीफ नोड्स ट्री के एक ऑपरेटर को दर्शाते हैं। उदाहरण: इनफिक्स एक्सप्रेशन प्राप्त करने के लिए जिसे आसानी से हल किया जा सकता है, हम

  1. C++ में 3n स्लाइस वाली पिज्जा C++ में 3n स्लाइस वाली पिज्जा

    समस्या विवरण मान लीजिए 3n स्लाइस वाली एक पिज्जा है जिसके स्लाइस विभिन्न आकार के हैं। मैं और मेरे दो दोस्त पिज्जा के स्लाइस निम्नानुसार लेंगे: मैं कोई भी पिज्जा स्लाइस चुनूंगा। मेरा दोस्त अमल मेरे चुने हुए स्लाइस के एंटी-क्लॉकवाइज दिशा में अगला स्लाइस लेगा। मेरा दोस्त बिमल मेरे चुने हुए स्लाइस के क