การเรียงสับเปลี่ยนขนาดใหญ่ที่สุดหลังจากสลับได้สูงสุด k ครั้งใน C++

โจทย์

ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมหาการเรียงสับเปลี่ยนขนาดใหญ่ที่สุดหลังจากสลับได้สูงสุด k ครั้ง

มาดูขั้นตอนการแก้ปัญหา

• กำหนดอาร์เรย์
• กำหนดอาร์เรย์เพื่อเก็บดัชนีขนาด n + 1
• วนลูปผ่านอาร์เรย์และเก็บดัชนีของแต่ละองค์ประกอบในอาร์เรย์ position
• เขียนลูปที่วนรอบจนถึง n และ k มากกว่า 0
  • เก็บตำแหน่งขององค์ประกอบ n - i ในตัวแปร temp
  • อัปเดตตำแหน่งขององค์ประกอบปัจจุบัน arr[i] ด้วย position[n - i]
  • อัปเดต position[n - i] ด้วยดัชนีปัจจุบัน i
  • สลับองค์ประกอบปัจจุบัน arr[i] กับ arr[temp] ลด k ลง 1
• พิมพ์องค์ประกอบของอาร์เรย์

ตัวอย่าง

มาดูโค้ดกัน

#include <bits/stdc++.h> 
using namespace std; 

void getLargestPermutation(int arr[], int n, int k) { 
    int position[n + 1]; 
    for (int i = 0; i < n; ++i) { 
        position[arr[i]] = i; 
    } 
    for (int i = 0; i < n && k; ++i) { 
        if (arr[i] == n - i) { 
            continue; 
        } 
        int temp = position[n - i]; 
        position[arr[i]] = position[n - i]; 
        position[n - i] = i; 
        swap(arr[temp], arr[i]); 
        --k; 
    } 
} 

int main() { 
    int arr[] = { 5, 3, 2, 6, 7, 1, 4 }; 
    int n = 7, k = 3; 
    getLargestPermutation(arr, n, k); 
    for (int i = 0; i < n; ++i) { 
        cout << arr[i]; 
    } 
    cout << endl; 
    return 0; 
}

ผลลัพธ์

หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้

7653214

สรุป

หากคุณมีคำถามในบทช่วยสอนนี้ ให้กล่าวถึงในส่วนความคิดเห็น