数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中带键的排列查询
假设我们有一个正整数数组 queries，这些整数介于 1 和 m 之间，我们需要根据以下规则处理所有查询 queries[i]（从 i=0 到 n，n 是 queries 的大小减 1）：
一开始，我们有排列 P=[1,2,3,...,m]。
对于当前的 i，找到 queries[i] 在排列 P 中的位置（从 0 开始索引），然后将它移动到排列 P 的开头。
我们需要找到一个包含给定查询结果的数组。
因此，如果输入类似于 queries = [3,1,2,1]，m = 5，那么输出将是 [2,1,2,1]，这是因为查询按以下方式处理：
对于索引 i = 0：queries[i]=3，P=[1,2,3,4,5]，3 在 P 中的位置是 2，然后将 3 移动到 P 的开头，得到 P=[3,1,2,4,5]。
对于索引 i = 1：queries[i]=1，P=[3,1,2,4,5]，1 在 P 中的位置是 1，然后将 1 移动到 P 的开头，得到 P=[1,3,2,4,5]。
对于索引 i = 2：queries[i]=2，P=[1,3,2,4,5]，2 在 P 中的位置是 2，然后将 2 移动到 P 的开头，得到 P=[2,1,3,4,5]。
对于索引 i = 3：queries[i]=1，P=[2,1,3,4,5]，1 在 P 中的位置是 1，然后将 1 移动到 P 的开头，得到 P=[1,2,3,4,5]。
最后，包含结果的数组是 [2,1,2,1]。
为了解决这个问题，我们将遵循以下步骤：
定义一个数组 ret
定义一个数组 v
对于初始化 i := 0，当 i − m，更新（增加 i 1），执行：
将 i + 1 插入到 v 的末尾
对于 q 中的每个值 x，执行：
pos := -1
定义一个数组 temp
对于初始化 i := 0，当 i < v 的大小，更新（增加 i 1），执行：
如果 v[i] 与 x 相同，则：
pos := i
退出循环
将 temp 的第一个元素插入到 temp 的索引 v[pos] 处
对于初始化 i := 0，当 i < v 的大小，更新（增加 i 1），执行：
如果 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, ]
115 次查看
