ধরুন আমাদের 1 এবং m-এর মধ্যে ধনাত্মক পূর্ণসংখ্যার একটি অ্যারে কোয়েরি আছে, আমাদের নিম্নলিখিত নিয়ম অনুসারে সমস্ত প্রশ্ন, প্রশ্ন [i] প্রক্রিয়া করতে হবে (i=0 থেকে n, n হল প্রশ্নের আকার - 1) পি>
-
শুরুতে, আমাদের P=[1,2,3,...,m] পারমুটেশন আছে।
-
বর্তমান i-এর জন্য, P-এ প্রশ্নগুলির অবস্থান খুঁজুন (0 থেকে সূচীকরণ) এবং তারপর এটিকে স্থানান্তর P-এর শুরুতে সরান।
প্রদত্ত প্রশ্নের জন্য ফলাফল সম্বলিত একটি অ্যারে খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি queries =[3,1,2,1], m =5 এর মত হয়, তাহলে আউটপুট হবে [2,1,2,1], এর কারণ হল ক্যোয়ারীগুলি অনুসরণ করে প্রক্রিয়া করা হয় -
-
সূচক i =0:queries[i]=3, P=[1,2,3,4,5], P-এ 3-এর অবস্থান হল 2, তারপর 3-কে P-এর শুরুতে সরান যার ফলে P=[3, 1,2,4,5]।
-
সূচক i =1:queries[i]=1, P=[3,1,2,4,5], P-এ 1-এর অবস্থান হল 1, তারপর 1-কে P-এর শুরুতে সরান যার ফলে P=[1, ৩,২,৪,৫]।
-
সূচক i =2:queries[i]=2, P=[1,3,2,4,5], P-এ 2-এর অবস্থান হল 2, তারপর 2-কে P-এর শুরুতে সরান যার ফলে P=[2, 1,3,4,5]।
-
সূচক i =3:queries[i]=1, P=[2,1,3,4,5], P-এ 1-এর অবস্থান হল 1, তারপর 1-কে P-এর শুরুতে সরান যার ফলে P=[1, 2,3,4,5]।
-
অবশেষে, ফলাফল ধারণকারী অ্যারে হল [2,1,2,1]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি অ্যারে ret সংজ্ঞায়িত করুন
-
একটি অ্যারে v
সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য i :=0, যখন i − m, আপডেট করুন (i 1 দ্বারা বাড়ান), করুন −
-
v
এর শেষে i + 1 ঢোকান
-
-
প্রতিটি মানের জন্য x q, করুন
-
অবস্থান :=-1
-
একটি অ্যারের তাপমাত্রা সংজ্ঞায়িত করুন
-
আরম্ভ করার জন্য i :=0, যখন i
-
যদি v[i] x এর মত হয়, তাহলে −
-
pos :=i
-
লুপ থেকে বেরিয়ে আসুন
-
-
-
সূচক v[pos>
-এ temp-এর প্রথম উপাদান প্রবেশ করান -
আরম্ভ করার জন্য i :=0, যখন i
-
যদি আমি pos এর মতই হয়, তাহলে -
-
নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
-
-
টেম্পের শেষে v[i] ঢোকান
-
-
v :=temp
-
ret এর শেষে pos সন্নিবেশ করুন
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> processQueries(vector<int>& q, int m) {
vector<int> ret;
vector<int> v;
for (int i = 0; i < m; i++)
v.push_back(i + 1);
for (int x : q) {
int pos = -1;
vector<int> temp;
for (int i = 0; i < v.size(); i++) {
if (v[i] == x) {
pos = i;
break;
}
}
temp.insert(temp.begin(), v[pos]);
for (int i = 0; i < v.size(); i++) {
if (i == pos)
continue;
temp.push_back(v[i]);
}
v = temp;
ret.push_back(pos);
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {3,1,2,1};
print_vector(ob.processQueries(v, 5));
} ইনপুট
{3,1,2,1}, 5 আউটপুট
[2, 1, 2, 1, ]
