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

मान लीजिए कि हमारे पास संभावित डुप्लिकेट के साथ पूर्णांकों की एक सरणी है, हमें किसी दिए गए लक्ष्य संख्या के सूचकांक को यादृच्छिक रूप से चुनना होगा। हम मान सकते हैं कि दी गई लक्ष्य संख्या सरणी में मौजूद होनी चाहिए। तो अगर सरणी [1,2,3,3,3] की तरह है, तो चुनें (3), यादृच्छिक रूप से 2, 3, 4 वापस आ सकता है।

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

• रिट:=- 1, सीएनटी:=1

• मैं के लिए 0 से वी के आकार में

  • अगर v[i] =लक्ष्य, तो

    • यदि यादृच्छिक संख्या mod cnt =0 है, तो ret =i

    • सीएनटी:=सीएनटी + 1

• वापसी रिट

उदाहरण (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