मान लीजिए हमारे पास 1 और m के बीच के पॉजिटिव इंटीजर्स का एक ऐरे queries है, हमें सभी क्वेरी को प्रोसेस करना है, queries[i] (i=0 से n तक, n queries का आकार - 1 है) निम्न नियमों के अनुसार:
शुरुआत में, हमारे पास पर्मुटेशन P=[1,2,3,...,m] है।
वर्तमान i के लिए, पर्मुटेशन P में queries[i] की स्थिति ढूंढें (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,3,2,4,5] हो।
इंडेक्स 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 बढ़ाते हुए, करें -
i + 1 को v के अंत में डालें
q के प्रत्येक मान x के लिए, करें
pos := -1
एक ऐरे temp परिभाषित करें
i := 0 से शुरू करें, जब i < v का आकार, i बढ़ाते हुए, करें -
यदि v[i], x के समान है, तो -
pos := i
लूप से बाहर आएं
temp के शुरुआत में v[pos] डालें
i := 0 से शुरू करें, जब i < v का आकार, i बढ़ाते हुए, करें -
यदि i, pos के समान है, तो -
बाकी भाग को अनदेखा करें, अगले इटरेशन पर जाएं
v[i] को temp के अंत में डालें
v := temp
pos को ret के अंत में डालें
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#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, ]
