อัลกอริธึมการกลับรายการสำหรับการหมุนขวาของอาร์เรย์โดยใช้ C++

ในบทความนี้ เราจะเข้าใจอัลกอริทึมการกลับรายการเพื่อหมุนอาร์เรย์ที่กำหนดโดยองค์ประกอบ k ไปทางขวา เช่น −

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 }

แนวทางในการหาทางออก

คุณสามารถแก้ปัญหานี้ได้อย่างง่ายดายโดยเลื่อนแต่ละองค์ประกอบไปทางขวาและทำซ้ำขั้นตอนนี้ k-time แต่จะใช้เวลามากขึ้นเนื่องจากความซับซ้อนของเวลาจะเป็น O(k * N)

อัลกอริธึมการกลับรายการ:การกลับรายการเป็นการกลับรายการอาร์เรย์ และการหมุนอาร์เรย์สามารถทำได้โดยการย้อนกลับช่วงองค์ประกอบบางช่วง ตามอัลกอริทึมนี้ −

• ขั้นแรก ย้อนกลับทั้งอาร์เรย์
• แก้ไข k ด้วยโมดูลัสของ k ด้วย N(ขนาดอาร์เรย์) เนื่องจาก k มากกว่า N
• ย้อนกลับองค์ประกอบ k แรกของอาร์เรย์เพื่อให้อยู่ในลำดับ
• จากนั้นย้อนกลับช่วงขององค์ประกอบที่เหลือ นั่นคือ จาก k เป็น N-1

ตัวอย่าง

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;
}

ผลลัพธ์

Array after rotating by k-elements : 6 2 4 5 4 6 2 6 43 7 3

บทสรุป

ในบทความนี้ เราได้พูดถึงปัญหาการหมุนขวาของอาร์เรย์โดยองค์ประกอบ k โดยใช้อัลกอริธึมการกลับรายการ เราได้กล่าวถึงอัลกอริธึมการกลับรายการคืออะไร และจะสามารถนำไปใช้เพื่อแก้ปัญหานี้ได้อย่างไร นอกจากนี้เรายังกล่าวถึงรหัส C ++ เพื่อแก้ปัญหานี้ เราสามารถเขียนโค้ดนี้ในภาษาอื่นๆ เช่น C, Java, Python เป็นต้น หวังว่าบทความนี้จะเป็นประโยชน์