Trong bài viết này, ta sẽ hiểu thuật toán đảo ngược để xoay một mảng cho trước k phần tử sang phải, ví dụ −
Input : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4 Output : { 43, 7, 3, 7, 4, 6, 2, 6 } Giải thích : Xoay mỗi phần tử mảng 4 phần tử sang phải cho { 43, 7, 3, 7, 4, 6, 2, 6 }. Input : arr[ ] = { 8, 5, 8, 2, 1, 4, 9, 3 }, k = 3 Output : { 4, 9, 3, 8, 5, 8, 2, 1 }Phương pháp tìm giải pháp
Bạn có thể dễ dàng giải quyết bài toán này bằng cách dịch từng phần tử sang phải và lặp lại k lần. Nhưng cách này tốn thời gian hơn vì độ phức tạp thời gian sẽ là O(k * N).
Thuật toán đảo ngược: Đảo ngược đảo ngược một mảng, và xoay mảng có thể thực hiện bằng cách đảo ngược một số phạm vi phần tử. Theo thuật toán này −
- Đầu tiên, đảo ngược toàn bộ mảng.
- Sửa đổi k bằng modulo k với N (kích thước mảng) vì k có thể lớn hơn N.
- Đảo ngược k phần tử đầu tiên của mảng để đưa về thứ tự.
- Sau đó đảo ngược phạm vi các phần tử còn lại, tức là từ k đến N-1.
Ví dụ
using namespace std; #include <bits/stdc++.h> void reverse(int nums[], int start,int end) { int temp=0; // đảo ngược mảng bằng cách hoán đổi phần tử đầu với phần tử cuối. while(start<=end){ temp=nums[end]; nums[end]=nums[start]; nums[start]=temp; start++; end--; } } int main() { int arr[] = {4, 6, 2, 6, 43, 7, 3, 6, 2, 4, 5 }; int N = sizeof(arr)/sizeof(arr[0]); int k = 4; // đảo ngược toàn bộ mảng reverse(arr, 0, N-1); k = k%N; // đảo ngược phạm vi phần tử 0 đến k-1. reverse(arr, 0, k-1); // đảo ngược phạm vi phần tử k đến cuối. reverse(arr, k, N-1); cout << "Array after rotating by k-elements : "; for(int i = 0;i<N;i++) cout << arr[i] << " "; return 0; }Kết quả
Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3
Kết luận
Trong bài viết này ta thảo luận bài toán xoay phải mảng k phần tử bằng thuật toán đảo ngược. Ta thảo luận thuật toán đảo ngược là gì và cách cài đặt để giải bài toán. Ta cũng thảo luận mã C++ để giải bài toán. Ta có thể viết mã này bằng bất kỳ ngôn ngữ nào khác như C, Java, Python, v.v. Hy vọng bạn thấy bài viết hữu ích.