Thuật toán đảo ngược để quay phải mảng bằng C ++

Trong bài viết này, chúng ta sẽ hiểu thuật toán Đảo ngược để xoay một mảng đã cho bởi k-phần tử sang bên phải, chẳng hạn như -

Input : arr[ ] = { 4, 6, 2, 6, 43, 7, 3, 7 }, k = 4
Output : { 43, 7, 3, 7, 4, 6, 2, 6 }
Explanation : Rotating each element of array by 4-element to the right gives { 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 tiếp cận để tìm ra giải pháp

Bạn có thể dễ dàng giải quyết vấn đề này bằng cách chuyển từng phần tử sang phải và lặp lại quy trình này k-lần. Nhưng điều này sẽ mất nhiều thời gian hơn vì độ phức tạp về thời gian của nó 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ột mảng có thể được 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, hãy đảo ngược toàn bộ mảng.
• Sửa k với môđun của k với N (kích thước mảng) vì k lớn hơn N.
• Đảo ngược k phần tử đầu tiên của mảng để có thứ tự.
• Sau đó, đảo ngược phạm vi các phần tử còn lại, tức là từ k thành N-1.

Ví dụ

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

void reverse(int nums[], int start,int end) {
   int temp=0;
   // reversing array with swapping start element with end element.
   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;
   // reversing whole array
   reverse(arr, 0, N-1);
   k = k%N;
   // reversing element range of 0 to k-1.

   reverse(arr, 0, k-1);
   // reversing element range of k to last element.
   reverse(arr, k, N-1);
   cout << "Array after rotating by k-elements : ";
   for(int i = 0;i<N;i++)
      cout << arr[i] << " ";
   return 0;
}

Đầu ra

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, chúng tôi đã thảo luận về vấn đề xoay phải của một mảng theo k-phần tử bằng cách sử dụng thuật toán Đảo ngược. Chúng tôi cũng đã thảo luận về mã C ++ để giải quyết vấn đề này. Chúng tôi 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 này hữu ích.