เราได้รับอาเรย์ตัวเลข 1 ถึง n ไม่มีตัวซ้ำ เป้าหมายคือหาจำนวนการ 'move-to-front' (นำสมาชิกไปวางหน้าสุด index 0) น้อยที่สุดเพื่อเรียงอาเรย์ เราจะลูปจากท้ายสู่หน้า หากสมาชิกอยู่ตำแหน่งที่ถูกต้องแล้ว ไม่ต้อง move มิฉะนั้นต้อง move สำหรับตัวเลข 1 ถึง n ตำแหน่งที่ถูกต้องของ arr[i] ควรอยู่ที่ index i+1 (arr[0]=1, arr[1]=2, ... arr[n-1]=n)
อินพุต
Arr[] = {4, 3, 2, 1}
เอาต์พุต
Minimum move-to-front operations: 3
คำอธิบาย − Pull 3: 3,4,2,1 count=1, Pull 2: 2,3,4,1 count=2, Pull 1: 1,2,3,4 count=3
อินพุต
Arr[] = {6, 1, 2, 5, 4, 3}
เอาต์พุต
Minimum move-to-front operations: 5
คำอธิบาย − Pull 5,4,3,2,1 ตามลำดับ รวม 5 ครั้ง
วิธีการที่ใช้ในโปรแกรมด้านล่าง
- อาเรย์ Arr[] เก็บตัวเลข 1 ถึง n
- size เก็บความยาว
- ฟังก์ชัน movetoFront(int arr[], int n) คืนค่าจำนวน move-to-front น้อยที่สุด
- count เริ่มต้น = n (กรณีแย่ที่สุด ทุกตัวต้อง move)
- ลูปจาก index สุดท้าย (n-1) ถึง 0 ถ้า arr[i] == count (อยู่ตำแหน่งถูกต้อง) count--
- จบลูป count จะเป็นคำตอบ
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
int movetoFront(int arr[], int n) {
int count = n;
for (int i = n-1; i >= 0; i--) {
if (arr[i] == count)
count--;
}
return count;
}
int main() {
int Arr[] = {5, 3, 4, 7, 2, 6, 1};
int size = 7;
cout << "Minimum 'move-to-front' to sort array: " << movetoFront(Arr, size);
return 0;
}
ผลลัพธ์
Minimum 'move-to-front' to sort array: 6
