C++-এ র‍্যান্ডম পিক ইন্ডেক্স

সম্ভাব্য ডুপ্লিকেটসহ একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে। একটি টার্গেট নম্বারের ইন্ডেক্স র‍্যান্ডমলি পিক করতে হবে। ধরে নেওয়া হয় টার্গেট নম্বরটি অ্যারেতে অবশ্যই আছে। উদাহরণ: অ্যারে [1,2,3,3,3] হলে pick(3) কল করলে ২, ৩, ৪ — যেকোনো একটি র‍্যান্ডমলি ফেরত দেবে।

সমাধানের ধাপগুলো:

• ret := -1, cnt := 1
• i = 0 থেকে v.size()-1 পর্যন্ত:
  • যদি v[i] == target:
    • যদি rand() % cnt == 0, ret = i
    • cnt++
• 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