C++ में रैंडम पिक इंडेक्स

मान लीजिए हमारे पास संभावित डुप्लिकेट के साथ पूर्णांकों की एक सरणी है, हमें दिए गए लक्ष्य संख्या का इंडेक्स यादृच्छिक रूप से चुनना है। हम मान सकते हैं कि दी गई लक्ष्य संख्या सरणी में मौजूद होनी चाहिए।

उदाहरण के लिए, यदि सरणी [1,2,3,3,3] जैसी है, तो pick(3), 2, 3, 4 को यादृच्छिक रूप से लौटा सकता है।

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

• ret := -1, cnt := 1
• i को 0 से v के आकार तक लूप करें
  • यदि v[i] = लक्ष्य, तो
    • यदि यादृच्छिक संख्या mod cnt = 0, तो ret = i
    • cnt := cnt + 1
• ret लौटाएं

उदाहरण (C++)

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

#include <bits/stdc++.h> using namespace std; class Solution {    public:    vector <int> v;    Solution(vector<int>& nums) {       srand(time(NULL));       v = nums;    }    int pick(int target) {       int ret = -1;       int cnt = 1;       for(int i = 0; i < v.size(); i++){          if(v[i] == target){             if(rand() % cnt++ == 0) ret = i;          }       }       return ret;    } }; main(){    vector<int> v = {1,2,3,3,3};    Solution ob(v);    cout << (ob.pick(3)); }

इनपुट

Initialize with [1,2,3,3,3] Call pick(3) to get random index positions

आउटपुट

4 3 4 2