คิวรี่บน Permutation พร้อม Key ใน C++

สมมติว่าเรามีอาร์เรย์ queries ค่าระหว่าง 1 ถึง m เริ่มจาก permutation P=[1,2,3,...,m] สำหรับแต่ละ query: หาตำแหน่งของ queries[i] ใน P (0-indexed) แล้วย้ายมาหน้าสุด เราต้องหาผลลัพธ์ทั้งหมด

ตัวอย่าง: queries = [3,1,2,1], m = 5 ผลลัพธ์ = [2,1,2,1]

วิธีแก้ปัญหา (Simulation)

1. สร้าง vector v = [1,2,...,m]
2. สำหรับแต่ละ query x:
   • หาตำแหน่ง pos ของ x ใน v
   • ย้าย x ไปหน้าสุด (insert at begin, erase at pos)
   • บันทึก pos
3. เวลา O(m * q) เหมาะกับ m ≤ 10^3

ตัวอย่างโค้ด C++

#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) temp.push_back(v[i]); 
            v = temp; 
            ret.push_back(pos); 
        } 
        return ret; 
    } 
}; 

int 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, ]