【02】右旋函数（C语言）

题目：给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。

1.暴力求解（轮转k次)

2. 三段逆置求解

①逆置函数

②轮转函数

3.空间换时间求解

题目：给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。

例如：

nums[7] = {1,2,3,4,5,6,7} k = 3

右旋三次后nums=[5,6,7,1,2,3,4]

1.暴力求解（轮转k次)

向右旋转 1 次：[7,1,2,3,4,5,6]

向右旋转 2 次：[6,7,1,2,3,4,5]

向右旋转 3 次：[5,6,7,1,2,3,4]

注：①如果k大于数组的总长度的话函数需要重复轮转多次，这时可以取模运算（也就是求余数）

②向右轮转时最后一个元素需要保存起来防止遗失，最后再将保存的最后一个元素的值赋给第一个元素完成一次轮转；

③运用for循环轮转k次；

void rotate(int* nums,int numsSize, int k)
{k %= numsSize;//k大于numsSize取模，避免不必要的计算,小于numsSize取模则没有影响int i = 0;int tmp = 0;for (i = 0; i < k; i++){int a = numsSize;tmp = nums[a - 1];创建一个变量保存最后的数字while (a >= 2)//当（a-2）>=0时判定条件结束{nums[a - 1] = nums[a - 2];//将数组前一个值赋给后一个a--;}nums[0] = tmp;//将tmp中保存的数组最后一个元素的值赋给数组第一个元素}
}

在vs2022上完整代码实现如下：

#include<stdio.h>
void rotate(int* nums,int numsSize, int k)
{k %= numsSize;//k大于numsSize取模，避免不必要的计算,小于numsSize取模则没有影响int i = 0;int tmp = 0;for (i = 0; i < k; i++){int a = numsSize;tmp = nums[a - 1];创建一个变量保存最后的数字while (a >= 2)//当（a-2）>=0时判定条件结束{nums[a - 1] = nums[a - 2];//将数组前一个值赋给后一个a--;}nums[0] = tmp;//将tmp中保存的数组最后一个元素的值赋给数组第一个元素}
}int main()
{int nums[7] = { 1,2,3,4,5,6,7 };int k = 3;rotate(nums,7, k);for (int i = 0; i < 7; i++)//打印轮转后的数组{printf("%d\n", nums[i]);}return 0;
}

运行结果如下：

以上就是暴力求解啦，关键是要一次一次的轮转，其时间复杂度为O( $n^{2}$ ),空间复杂度为O(1),对每次轮转的代码理解也极其重要哦~

2. 三段逆置求解

@_@: "一个不一样的玩法，极其灵活的同时又极其难想，但它又像欧亨利式的结尾那般出人意料却又在情理之中"。

nums=[1,2,3,4,5,6,7] k=3 n=7

①逆置函数

void reverse(int* nums, int left, int right)//逆置函数
{int tmp = 0;//创建一个中间变量while (left < right)//当左边等于右边时逆置结束{tmp = nums[right];nums[right] = nums[left];nums[left] = tmp;//左边和右边交换left++;right--;}}

②轮转函数

void rotate(int* nums, int numsSize, int k)//轮转函数
{k %= numsSize;reverse(nums, 0, numsSize - k - 1);//前n-k个逆置reverse(nums,0,3)reverse(nums, numsSize - k, numsSize - 1);后k个逆置//reversez(nums,4,6)reverse(nums, 0, numsSize - 1);//整体逆置reverse(nums,0,6)}

在vs2022上运行代码如下：

#include<stdio.h>
void reverse(int* nums, int left, int right)
{int tmp = 0;while (left < right){tmp = nums[right];nums[right] = nums[left];nums[left] = tmp;left++;right--;}
}
void rotate(int* nums, int numsSize, int k)
{k %= numsSize;reverse(nums, 0, numsSize - k - 1);//reverse(nums,0,3)reverse(nums, numsSize - k, numsSize - 1);//reversez(nums,4,6)reverse(nums, 0, numsSize - 1);//reverse(nums,0,6)}
int main()
{int nums[7] = { 1,2,3,4,5,6,7 };int k = 3;rotate(nums, 7, 3);for (int i = 0; i < 7; i++){printf("%d\n", nums[i]);}return 0;
}

结果如下：

以上就是三段逆置啦，其时间复杂度为O(n),空间复杂度为O(1);最重要的就是它的思路三段逆置，其次就是逆置函数的实现。

3.空间换时间求解

开始：nums=[1,2,3,4,5,6,7]

结果：nums=[5,6,7,1,2,3,4]

所以如果有另外一个数组a先将nums中的{5，6，7}保存下来，再将{1，2，3，4}保存即可得到a=[5,6,7,1,2,3,4];最后将a拷贝到nums中即可，其时间复杂度较暴力求解大大减少为O(n)，但空间复杂度变多为O(n);

注：①使用malloc开辟空间给a；

②使用memcpy函数来拷贝；（malloc、memcpy详情可见上一篇博客动态内存函数介绍【C语言】动态内存函数介绍-CSDN博客）

③malloc开辟的空间要记得free释放掉，并将指针置空哦

代码如下：

void rotate(int* nums, int numsSize, int k)
{k %= numsSize;int* a = (int*)malloc(sizeof(int) * numsSize);memcpy(a, nums + k +1 , sizeof(int) * (numsSize - k -1));//先将nums中的{5，6，7}保存下来memcpy(a + k,nums, sizeof(int) *(k+1));//再将{1，2，3，4}保存memcpy(nums, a, sizeof(int) * numsSize);//最后将a拷贝到nums中free(a);//释放掉开辟的空间a = NULL;//置空指针
}

在vs2022上完整运行代码如下：

void rotate(int* nums, int numsSize, int k)
{k %= numsSize;int* a = (int*)malloc(sizeof(int) * numsSize);memcpy(a, nums + k +1 , sizeof(int) * (numsSize - k -1));memcpy(a + k,nums, sizeof(int) *(k+1));memcpy(nums, a, sizeof(int) * numsSize);free(a);a = NULL;
}
int main()
{int nums[7] = { 1,2,3,4,5,6,7 };int k = 3;rotate(nums, 7, 3);for (int i = 0; i < 7; i++){printf("%d\n", nums[i]);}return 0;
}

运行结果如下：