C++のキーを使用した順列に関するクエリ

1からmまでの正の整数の配列クエリがあるとすると、次のルールに従って、すべてのクエリ、querys [i]（i =0からn、nはクエリのサイズ-1）を処理する必要があります-

• 最初に、順列P =[1,2,3、...、m]があります。

• 現在のiについて、順列P（0からのインデックス付け）でquerys [i]の位置を見つけ、これを順列Pの先頭に移動します。

指定されたクエリの結果を含む配列を見つける必要があります。

したがって、入力がクエリ=[3,1,2,1]、m =5の場合、出力は[2,1,2,1]になります。これは、クエリが次のように処理されるためです-

• インデックスi=0の場合：querys [i] =3、P =[1,2,3,4,5]、Pの3の位置は2です。次に、3をPの先頭に移動すると、P =[3、 1,2,4,5]。

• インデックスi=1の場合：querys [i] =1、P =[3,1,2,4,5]、Pの1の位置は1です。次に、1をPの先頭に移動すると、P=[1になります。 3,2,4,5]。

• インデックスi=2の場合：querys [i] =2、P =[1,3,2,4,5]、Pの2の位置は2です。次に、2をPの先頭に移動すると、P =[2、 1,3,4,5]。

• インデックスi=3の場合：querys [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を挿入します

• qの値xごとに、実行

  • pos：=-1

  • アレイの温度を定義する

  • 初期化i：=0の場合、i

    • v [i]がxと同じ場合、-

      • pos：=i

      • ループから出てきます

  • tempの最初の要素をインデックスv[pos]

    のtempに挿入します

  • 初期化i：=0の場合、i

    • iがposと同じ場合、-

      • 次の部分を無視し、次の反復にスキップします

    • tempの最後にv[i]を挿入します

  • v：=temp

  • retの最後にposを挿入します

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