1에서 m 사이의 양의 정수 배열 쿼리가 있다고 가정하고 다음 규칙에 따라 모든 쿼리 쿼리[i](i=0에서 n, n은 쿼리 크기 - 1)를 처리해야 합니다. 피>
-
처음에는 순열 P=[1,2,3,...,m]이 있습니다.
-
현재 i의 경우 순열 P(0부터 인덱싱)에서 쿼리[i]의 위치를 찾은 다음 순열 P의 시작 부분으로 이동합니다.
주어진 쿼리에 대한 결과가 포함된 배열을 찾아야 합니다.
따라서 입력이 쿼리 =[3,1,2,1], m =5와 같으면 출력은 [2,1,2,1]이 됩니다. 이는 쿼리가 다음과 같이 처리되기 때문입니다 -
-
인덱스 i =0의 경우:쿼리[i]=3, P=[1,2,3,4,5], P에서 3의 위치는 2이고 3을 P의 시작 부분으로 이동하여 P=[3, 1,2,4,5].
-
인덱스 i =1의 경우:쿼리[i]=1, P=[3,1,2,4,5], P에서 1의 위치는 1이고 P의 시작 부분으로 1을 이동하여 P=[1, 3,2,4,5].
-
인덱스 i =2의 경우:쿼리[i]=2, P=[1,3,2,4,5], P에서 2의 위치는 2이고 2를 P의 시작 부분으로 이동하여 P=[2, 1,3,4,5].
-
인덱스 i =3의 경우:쿼리[i]=1, P=[2,1,3,4,5], P에서 1의 위치는 1이고 P의 시작 부분으로 1을 이동하여 P=[1, 2,3,4,5].
-
마지막으로 결과를 포함하는 배열은 [2,1,2,1]입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ret 배열 정의
-
배열 정의 v
-
initialize i :=0의 경우 i − m일 때 업데이트(i를 1만큼 증가), −
-
v
끝에 i + 1 삽입
-
-
q의 각 값 x에 대해 수행
-
위치 :=-1
-
어레이 온도 정의
-
initialize i :=0의 경우 i
-
v[i]가 x와 같으면 -
-
위치 :=나는
-
루프에서 나오세요
-
-
-
인덱스 v[pos]
에 있는 temp에 temp의 첫 번째 요소를 삽입합니다. -
initialize i :=0의 경우 i
-
i가 pos와 같으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
temp의 끝에 v[i] 삽입
-
-
v :=온도
-
ret 끝에 pos 삽입
-
-
리턴 렛
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#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, ]