详解数组的轮转
𝙉𝙞𝙘𝙚!!👏🏻???????👏🏻??????? 👏🏻?????:Solitary-walk
? ? ? ?? ? ━━━┓
? ? ?- 个性标签 - ：来于“云”的“羽球人”。 Talk is cheap. Show me the code
┗━━━━━━━ ?? ?本人座右铭 ： ? 欲达高峰,必忍其痛;欲戴王冠,必承其重。
👑💎💎👑💎💎👑?
💎💎💎自💎💎💎
💎💎💎信💎💎💎
👑💎💎 💎💎👑 ? ?希望在看完我的此篇博客后可以对你有帮助哟👑👑💎💎💎👑👑 ? 此外，希望各位大佬们在看完后，可以互赞互关一下，看到必回
👑👑👑💎👑👑👑
目录：
一：题目
二：解题思路的分析
三：触类旁通
四：结语
一：题目
?二：解题思路的分析
1：暴力求解
1）当 k = 1,要想达到最终结果我们只需要将数组最后一个元素保留，其余元素依次为我的元素 7让道，（依次往后挪动）
2）那么问题又来了，到底是从后往前挪动 还是从前往后挪动数据
?当然是从后往前挪动了，你想对了吗？？？（因为从前往后挪动数据会造成数据的覆盖，全部是数据2）
当 k = 2 ，我们直接接着再? k = 1的那个图的基础上进行同样的挪动，这里用循环来实现就可以
void rotate(int* nums, int numsSize, int k)
{
k %= numsSize;//避免k的大小超过数组的大小，造成旋转无效 k = 8,numSize = 4,此时不需要轮转
//暴力求解
// 数组最后一个元素进行保留，其余元素一次后挪动
for(int j = 0 ;j<k;j++)
{
int temp = *(nums+numsSize-1);
//挪动数据：从后往前挪动
for(int i = numsSize-1;i >= 1;i--)
{
*(nums+i) = *(nums+i-1);
}
*(nums) = temp;
}
}注意这里有个坑：就是当k大于数组的大小的时候要进行 k对numsSize进行取余，避免无效的旋转
?k = 9，这里只需要进行1次旋转就可以
暴力求解对应的事件复杂度是? O（N^2） ,在力扣上是跑不过去的
2： 借助3段逆置?
核心思想：
1）先对前 n-k 个元素进行逆置
2）在对后 k 个元素进行逆置
3）最后再对整个数组进行逆置
注意： 以上的顺序不能颠倒；其次就是进行下标传参的时候要仔细
?这里我们借助Reverse(int*arr,int lef,int rig)这个函数来进行逆置
void Reverse(int* arr, int lef, int rig)
{
while (lef < rig)
{
int tmp = *(arr + lef);//便于进行交换
*(arr + lef) = *(arr + rig);
*(arr + rig) = tmp;
//类似于双指针的思想
lef++;
rig--;
}
}此方法对应的时间复杂度是 O（N），空间复杂度O（1）
三：触类旁通
借助三段逆置的思想实现字符串的逆置
题目：
?把字符串 "abcd" 经过2次旋转后实现? "cdab"
?前? n - k 对应的
?后k对应的
最后整个数组对应的
ok~~~话不多说，咱代码见
void Reverse(char* str, int left, int right)
{
// 逆置数组
while (left < right)
{
int tmp = *(str + left);
*(str + left) = *(str + right);
*(str + right) = tmp;
left++;
right--;
}
}
void LeftRound3(char* str, int k)
{
// 局部旋转 只需进行翻转3次即可
//逆置数组 确定下标位置
int len = strlen(str);
int k = k % len; // 避免无效旋转
Reverse(str,0,k - 1);
Reverse(str, k,len-1);
Reverse(str, 0, len - 1);
}结语：以上就是小生今日为大家要share的内容，要是感觉还不错的话，给个关注，咱一波赞走起，看到必回~~~
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！