資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
