【C语言指南】轮转数组
【摘要】 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
思路一：思路一:两层循环移动元素
思路二:数组三段逆置
一、问题描述
注意：
根据题目示例，右转是每次将数组的最右边的一个元素移动到数组最左边
二、解决思路
思路一:两层循环移动元素
时间复杂度O（n^2）
将数组旋转（k%numsSize)轮，每轮将最后一个元素移动到最前面，其他元素向后移动一位，元素总共移动numsSize次
某种程度上来说，这种解法算是暴力解法，效率是比较低的
思路二:数组三段逆置
时间复杂度O（n）
k=k%numsSize（实际旋转次数）
先将数组左半段 下标0到numsSize-k-1逆置
再将数组右半段 下标numsSize-k到numsSize-1逆置
最后将数组整体 下标0到numsSize-1逆置
三段逆置代码几乎是相同的，所以可以单独封装一个逆置函数
三、C语言实现代码
思路一实现代码：
void rotate(int* nums, int numsSize, int k)
{
k%=numsSize;
while(k--)//外循环，控制轮转次数
{
int tmp=nums[numsSize-1];//先保存尾部元素
for(int i=numsSize-1;i>0;i--)//内层循环控制元素移动
{
nums[i]=nums[i-1];
}
nums[0]=tmp;
}
}思路二实现代码：
void reverse(int* nums,int left,int right)//逆置函数
{
while(left<right)
{
int tmp=nums[left];
nums[left]=nums[right];
nums[right]=tmp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k)
{
k%=numsSize;
reverse(nums,0,numsSize-k-1);//左段逆置
reverse(nums,numsSize-k,numsSize-1);//右段逆置
reverse(nums,0,numsSize-1);//整体逆置
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）