使用 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 的模数修改 k，N(array size)因为 k 大于 N。

• 反转数组的前 k 个元素以获取顺序。

• 然后反转剩余元素的范围，即从k到N-1。

示例

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

void reverse(int nums[], int start,int end) {
   int temp=0;
   // 使用结束元素交换开始元素的反转数组。
   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;
   // 反转整个数组
   reverse(arr, 0, N-1);
   k = k%N;
   // 反转元素范围为 0 到 k-1。

   reverse(arr, 0, k-1);
   // 将 k 的元素范围反转到最后一个元素。
   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

结论

在本文中，我们讨论了使用 Reversal 由 k 个元素向右旋转数组的问题，algorithm.We讨论了什么是反转算法以及如何实现它来解决这个问题。我们还讨论了 C++ 代码来解决这个问题。我们可以用任何其他语言（如 C、Java、Python 等）编写此代码。希望本文对您有所帮助。