Truy vấn về hoán vị bằng khóa trong C ++

Giả sử chúng ta có một mảng truy vấn các số nguyên dương từ 1 đến m, chúng ta phải xử lý tất cả các truy vấn, truy vấn [i] (từ i =0 đến n, n là kích thước của truy vấn - 1) theo quy tắc sau -

• Ở phần đầu, ta có hoán vị P =[1,2,3, ..., m].

• Đối với i hiện tại, hãy tìm vị trí của các truy vấn [i] trong hoán vị P (lập chỉ mục từ 0) và sau đó di chuyển nó vào đầu hoán vị P.

Chúng ta phải tìm một mảng chứa kết quả cho các truy vấn đã cho.

Vì vậy, nếu đầu vào giống như các truy vấn =[3,1,2,1], m =5, thì đầu ra sẽ là [2,1,2,1], điều này là do các truy vấn được xử lý như sau -

• Đối với chỉ mục i =0:truy vấn [i] =3, P =[1,2,3,4,5], vị trí của 3 trong P là 2, sau đó di chuyển 3 về đầu P dẫn đến P =[3, 1,2,4,5].

• Đối với chỉ mục i =1:truy vấn [i] =1, P =[3,1,2,4,5], vị trí của 1 trong P là 1, sau đó di chuyển 1 đến đầu P dẫn đến P =[1, 3,2,4,5].

• Đối với chỉ mục i =2:truy vấn [i] =2, P =[1,3,2,4,5], vị trí của 2 trong P là 2, sau đó di chuyển 2 về đầu P dẫn đến P =[2, 1,3,4,5].

• Đối với chỉ mục i =3:truy vấn [i] =1, P =[2,1,3,4,5], vị trí của 1 trong P là 1, sau đó di chuyển 1 đến đầu P dẫn đến P =[1, 2,3,4,5].

• Cuối cùng, mảng chứa kết quả là [2,1,2,1].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định ret mảng

• Xác định một mảng v

• để khởi tạo i:=0, khi i - m, cập nhật (tăng i lên 1), thực hiện -

  • chèn i + 1 vào cuối v

• với mỗi giá trị x trong q, thực hiện

  • pos:=-1

  • Xác định tạm thời mảng

  • để khởi tạo i:=0, khi i

    • nếu v [i] giống với x thì -

      • pos:=i

      • Ra khỏi vòng lặp

  • chèn phần tử đầu tiên của tạm thời vào tạm thời tại chỉ mục v [pos]

  • để khởi tạo i:=0, khi i

    • nếu tôi giống với pos, thì -

      • Bỏ qua phần sau, chuyển sang phần tiếp theo

    • chèn v [i] vào cuối tạm thời

  • v:=temp

  • chèn pos vào cuối ret

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

#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));
}

Đầu vào

{3,1,2,1}, 5

Đầu ra

[2, 1, 2, 1, ]