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