在C ++中使用键进行排列的查询
假设我们有一个介于1和m之间的正整数的数组查询，我们必须根据以下规则处理所有查询querys[i]（从i=0到n，n是查询的大小-1）-
首先，我们有排列P=[1,2,3，...，m]。
对于当前的i，找到查询[i]在置换P中的位置（从0开始索引），然后在置换P的开头移动它。
我们必须找到一个包含给定查询结果的数组。
因此，如果输入类似于查询=[3,1,2,1]，m=5，则输出将为[2,1,2,1]，这是因为查询的处理如下-
对于索引i=0：query[i]=3，P=[1,2,3,4,5]，P中3的位置为2，然后将3移到P的开头，得出P=[3，1,2,4,5]。
对于索引i=1：query[i]=1，P=[3,1,2,4,5]，P中1的位置为1，然后将1移到P的开头，得出P=[1，3,2,4,5]。
对于索引i=2：query[i]=2，P=[1,3,2,4,5]，P在2中的位置为2，然后将2移到P的开头，得出P=[2，1,3,4,5]。
对于索引i=3：query[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相同，则-
在temp的末尾插入v[i]
忽略以下部分，跳至下一个迭代
如果v[i]与x相同，则-
pos：=我
从循环中出来
pos：=-1
定义阵列温度
对于初始化i：=0，当i<v的大小时，更新（将i增加1），执行-
在索引v[pos]的temp中插入temp的第一个元素
对于初始化i：=0，当i<v的大小时，更新（将i增加1），执行-
v：=温度
在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, ]