แบบสอบถามเกี่ยวกับการเปลี่ยนแปลงด้วยคีย์ใน C++

สมมติว่าเรามีการสืบค้นอาร์เรย์ของจำนวนเต็มบวกระหว่าง 1 ถึง m เราต้องประมวลผลการสืบค้นทั้งหมด การสืบค้น[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:การสืบค้น[i]=3, P=[1,2,3,4,5] ตำแหน่งของ 3 ใน P คือ 2 จากนั้นย้าย 3 ไปยังจุดเริ่มต้นของ P ส่งผลให้ P=[3 1,2,4,5].

• สำหรับดัชนี i =1:การสืบค้น[i]=1, P=[3,1,2,4,5] ตำแหน่งของ 1 ใน P คือ 1 จากนั้นย้าย 1 ไปยังจุดเริ่มต้นของ P ส่งผลให้ P=[1, 3,2,4,5].

• สำหรับดัชนี i =2:การสืบค้น[i]=2, P=[1,3,2,4,5] ตำแหน่งของ 2 ใน P คือ 2 จากนั้นย้าย 2 ไปยังจุดเริ่มต้นของ P ส่งผลให้ P=[2, 1,3,4,5].

• สำหรับดัชนี i =3:คำสั่ง[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

• สำหรับแต่ละค่า x ใน q ทำ

  • ตำแหน่ง :=-1

  • กำหนดอุณหภูมิอาร์เรย์

  • สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • ถ้า v[i] เหมือนกับ x แล้ว −

      • pos :=ฉัน

      • ออกจากวง

  • แทรกองค์ประกอบแรกของ temp ลงใน temp ที่ index v[pos]

  • สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

    • ถ้าฉันเหมือนกับ pos แล้ว −

      • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

    • ใส่ v[i] ที่จุดสิ้นสุดของอุณหภูมิ

  • v :=อุณหภูมิ

  • ใส่ 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, ]