详解数组的轮转

2023-12-31 22:46:19

𝙉𝙞𝙘𝙚!!👏🏻???????👏🏻??????? 👏🏻?????: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的内容,要是感觉还不错的话,给个关注,咱一波赞走起,看到必回~~~

文章来源:https://blog.csdn.net/X_do_myself/article/details/135317562
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。