使用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 次，您可以輕鬆解決此問題。但這會花費更多時間，因為其時間複雜度為O(k * N)。

反轉演算法：反轉是反轉數組，旋轉數組可以透過反轉某些元素範圍來完成。根據這個演算法 -

• 首先，反轉整個陣列。
• 用 k 與 N（陣列大小）的模來修改 k，因為 k 是大於 N。
• 反轉數組的前 k 個元素以使其按順序排列。
• 然後反轉剩餘元素的範圍，即從 k 到 N-1。
• li>

範例

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 等）來編寫此程式碼。希望本文對您有幫助。

以上是使用C++編寫的陣列右旋轉的反轉演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！