使用 C++ 的数组旋转的反转算法

在给定的问题中,我们得到一个数组,我们需要使用反转算法将数组旋转 d 个元素,例如 -

Input : arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2

Output : arr[] = [3, 4, 5, 6, 7, 1, 2]

Explanation : As you can see we have to rotate this array by d = 2 but our main task is to achieve this by using a reversal technique.

我们通过反转技术对阵列的旋转进行了一些计算,我们得出的结论是 -

  • 首先,我们反转数组的前 d 个元素。

  • 其次,我们反转剩余的元素。

  • 第三,我们反转整个数组。

通过应用这三个步骤,我们可以得到我们的旋转数组。

寻找解决方案的方法

在这个问题中,首先,我们要制作一个反转元素的函数;现在我们按照上面给出的步骤

示例

#include <bits/stdc++.h>

using namespace std;

void reverseArray(int arr[], int start, int end) { // 我们的反转算法

   while (start < end) { // 如果开始变得等于结束我们打破循环

      int temp = arr[start];

      arr[start] = arr[end];

      arr[end] = temp;

      start++;

      end--;

   }

   return ;

}

void Rotate(int arr[], int d, int n) { // 旋转功能

   if (d == 0) // 无需轮换

      return;

   d = d % n; // 当 d 等于 n 时,我们的数组就变成了它的原始形式

   reverseArray(arr, 0, d - 1); // 反转前 d 个元素

   reverseArray(arr, d, n - 1); // 反转剩余元素

   reverseArray(arr, 0, n - 1); // 反转整个数组

   return ;

}

int main() {

   int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; // 给定数组

   int n = sizeof(arr) / sizeof(arr[0]); // 我们数组的大小

   int d = 2;

   Rotate(arr, d, n);

   for(int i = 0; i < n; i++) // 打印数组

      cout << arr[i] << " ";

   cout << "\n";

   return 0;

}

输出结果
3 4 5 6 7 1 2

上面代码的解释

在上面的方法中,我们首先创建了我们的反转技术,它将采用三个参数,即数组、起始索引和结束索引,现在将我们的数组从开始到结束反转。正如我们之前开发我们的算法一样,我们将使用此函数应用该算法。我们首先反转前 d 个元素。其次,我们反转剩余的元素,最后反转整个数组。结果,我们的数组旋转了 d。在旋转函数中,我们使 d = d % n。这是因为如果我们旋转数组的前 n 个元素,我们得到的答案将与以前相同,所以这就是我们用 n 对 d 进行模的原因。

结论

在本文中,我们解决了将逆向算法应用于数组旋转的问题。我们还学习了针对此问题的 C++ 程序以及解决此问题的完整方法 (Normal)。我们可以用其他语言编写相同的程序,例如 C、java、python 和其他语言。我们希望这篇文章对您有所帮助。

以上是 使用 C++ 的数组旋转的反转算法 的全部内容, 来源链接: utcz.com/z/355722.html

回到顶部