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

介绍

在日常生活中,对于一个数组进行反转是一项很常见的操作。反转一般会话通读为数组元素的位置顺序,将最右边的元素移动到最左边,以此类推,最终实现数组元素位置的倒序。本篇文章将介绍使用C++编写的数组右旋转的反转算法。

什么是数组右旋转?

数组的旋转

数组旋转操作意味着将数组中某些元素的位置翻转。数组旋转有三种常见的类型:左旋转,右旋转,和缺口旋转。左旋转和右旋转表示数组中的元素循环移位左侧或右侧。一个示例如下:

> 假设初始的数组为[1, 2, 3, 4, 5, 6, 7],如果左旋转3位,数组变成[4, 5, 6, 7, 1, 2, 3],如果右旋转3位,数组变成[5, 6, 7, 1, 2, 3, 4]。

缺口旋转是先将数组劈成两半,然后将其中一半反转,最后将两半合并。这种旋转可以解决某些问题例如搜索旋转排序数组。本文主要讨论的是右旋转。

数组右旋转

数组右旋转意味着将数组的最右边的元素移动到最左边,以此类推。例如,数组[1, 2, 3, 4, 5]右旋转2步,成为[4, 5, 1, 2, 3]。

实现算法

实现数组右旋转的反转算法,我们需要使用两个指针left和right,分别指向数组的头和尾。我们可以翻转从left到right的元素,然后将left和right向中间移动,不断重复此过程,直到left>right。下面是实现代码:

void reverse(vector<int> &nums, int left, int right){

while(left<right) {

swap(nums[left], nums[right]);

left++;

right--;

}

}

void rotate(vector<int>& nums, int k) {

int n = nums.size();

k %= n;

reverse(nums, 0, n - 1);

reverse(nums, 0, k - 1);

reverse(nums, k, n - 1);

}

在上面的代码中,首先定义了一个翻转函数reverse(),该函数接受一个数组、左侧索引left和右侧索引right,然后翻转从左到右的元素。然后定义数组右旋转函数rotate(),该函数接受一个数组和要移动的步数k。接下来,我们需要计算k值以使其小于数组长度,接着使用reverse()函数翻转整个数组,然后再使用reverse()函数翻转前k个元素,最后再使用reverse()函数翻转(k, n-1)范围内的元素,其中n是数组长度。

代码解析

reverse()函数

下面是reverse()函数的代码:

void reverse(vector<int>& nums, int left, int right) {

while(left<right) {

swap(nums[left], nums[right]);

left++;

right--;

}

}

reverse()函数使用左侧和右侧索引将数组翻转。在while循环中,左侧指针left向右移动,右侧指针right向左移动,每次交换left和right指针的元素,直到左指针大于右指针。这个函数是算法最重要的部分,因为这个函数将在各种翻转和旋转操作中使用。

rotate()函数

下面是rotate()函数的代码:

void rotate(vector<int>& nums, int k) {

int n = nums.size();

k %= n;

reverse(nums, 0, n - 1);

reverse(nums, 0, k - 1);

reverse(nums, k, n - 1);

}

rotate()函数执行以下操作:

1. 计算要移动的步数k,以使其小于数组长度

2. 使用reverse()函数旋转整个数组

3. 使用reverse()函数旋转前k个元素

4. 使用reverse()函数旋转(k, n-1)范围内的元素,其中n是数组长度。

测试代码

下面是测试代码:

int main() {

vector<int> nums = {1, 2, 3, 4, 5, 6, 7};

int k = 3;

rotate(nums, k);

for (auto num : nums)

cout << num << " ";

return 0;

}

上面的代码将数组[1, 2, 3, 4, 5, 6, 7]右旋转了3个步骤,并打印出结果[5, 6, 7, 1, 2, 3, 4]。

总结

本篇文章介绍了使用C++编写的数组右旋转的反转算法。我们使用左侧和右侧指针来交换元素的位置,最终得到一个右旋转的数组。此算法的关键是reverse()函数,其将我们在翻转和旋转中使用。我们通过测试代码验证了算法的正确性。

后端开发标签