सी ++ में कुंजी के साथ क्रमपरिवर्तन पर प्रश्न

मान लीजिए कि हमारे पास 1 और m के बीच सकारात्मक पूर्णांकों की एक सरणी क्वेरी है, हमें सभी प्रश्नों, प्रश्नों को संसाधित करना है [i] (i =0 से n तक, n प्रश्नों का आकार है -1) निम्नलिखित नियमों के अनुसार -

• शुरुआत में, हमारे पास क्रमचय P=[1,2,3,...,m] है।

• वर्तमान i के लिए, क्रमचय P (0 से अनुक्रमण) में प्रश्नों की स्थिति [i] ज्ञात करें और फिर इसे क्रमचय P की शुरुआत में स्थानांतरित करें।

हमें दिए गए प्रश्नों के परिणाम वाली एक सरणी ढूंढनी है।

इसलिए, यदि इनपुट प्रश्नों की तरह है =[3,1,2,1], एम =5, तो आउटपुट [2,1,2,1] होगा, ऐसा इसलिए है क्योंकि प्रश्नों को निम्नानुसार संसाधित किया जाता है -

• अनुक्रमणिका i =0 के लिए:क्वेरीज़ [i] =3, P =[1,2,3,4,5], P में 3 की स्थिति 2 है, फिर 3 को P की शुरुआत में ले जाएँ जिसके परिणामस्वरूप P=[3, 1,2,4,5].

• अनुक्रमणिका के लिए i =1:क्वेरीज़[i]=1, P=[3,1,2,4,5], P में 1 की स्थिति 1 है, फिर 1 को P की शुरुआत में ले जाएँ जिसके परिणामस्वरूप P=[1, 3,2,4,5].

• अनुक्रमणिका i =2 के लिए:क्वेरीज़[i]=2, P=[1,3,2,4,5], P में 2 की स्थिति 2 है, फिर 2 को P की शुरुआत में ले जाएं जिसके परिणामस्वरूप P=[2, 1,3,4,5].

• अनुक्रमणिका के लिए i =3:क्वेरीज़[i]=1, P=[2,1,3,4,5], P में 1 की स्थिति 1 है, फिर 1 को P की शुरुआत में ले जाएँ जिसके परिणामस्वरूप P=[1, 2,3,4,5].

• अंत में, परिणाम वाली सरणी [2,1,2,1] है।

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

• एक सरणी रिट परिभाषित करें

• सरणी को परिभाषित करें v

• इनिशियलाइज़ i :=0 के लिए, जब i - m, अपडेट करें (i को 1 से बढ़ाएँ), करें -

  • v के अंत में i + 1 डालें

• q में प्रत्येक मान x के लिए, करें

  • स्थिति :=-1

  • एक सरणी अस्थायी परिभाषित करें

  • इनिशियलाइज़ i:=0 के लिए, जब i

    • अगर v[i] x के समान है, तो -

      • स्थिति :=मैं

      • लूप से बाहर आएं

  • सूचकांक v[pos]

    . पर अस्थायी में अस्थायी का पहला तत्व डालें

  • इनिशियलाइज़ i:=0 के लिए, जब i

    • अगर मैं पॉज़ के समान हूं, तो -

      • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

    • अस्थायी के अंत में v[i] डालें

  • वी:=अस्थायी

  • रिट के अंत में पोज़ डालें

• वापसी रिट

उदाहरण

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

#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, ]