求旋转数组(左旋和右旋)的常用两个方法(详解)

简介: 求旋转数组(左旋和右旋)的常用两个方法(详解)

方法1:暴力求解法


1.1 解析:


这种方法很好想,也很好理解,但是效率不怎么高!!!


左旋:对于一组数据1 2 3 4 5 6 7 8 9;假设我们是左旋1次;结果是2 3 4 5 6 7 8 9 1;是怎么得到的呢?我们不难发现其实是先把第一个数据拿出来,然后把后面的n-1个数据依次往前移;最后在把首元素的数据放到最后面就行啦,这就需要写一个循环!!!这是左旋转1次的结果,那么如果要旋转k次了怎么办?再在外面写一层循环不就好啦!


右旋:对于一组数据1 2 3 4 5 6 7 8 9;假设我们是右旋1次;结果是9 1 2 3 4 5 6 7 8 ;同样的思路,我们需要把最后一个数据拿出来,然后把前面n-1个数据往后移;最后再把最后一个元素的数据放到最前面就行啦,同样也是两层循环!


所以这种方法很好想,也很容易理解,时间复杂度是O(n*k);空间复杂度为O(1)。


1.2 具体代码:


左旋代码:

aaa7c5c906be4538a59e51be1064964a.png

a4ef846e722441c786ec433351e779ee.png

右旋代码:


da089671c24f473382d86c866f8096a4.png


4ed4b365ebfc41a79b4ce74e0463a64b.png


1.3 代码解析:


我们不难发现无论是左旋还是右旋最主要的就是移位部分要处理好:


对于左旋:我们把第一个元素取出来,用tmp存起来===》tmp=arr[0];然后在从前面第二个元素依次往前移,下标是依次-1的,所以是arr[j]=arr[j+1];最后令最后一个元素的位置arr[sz-1]=tmp即可;这里我们只强调两点:


1.只能从第二个元素依次往前移,而不能从最后一个元素往前移,因为这样会造成数据的覆盖!!!所以我们是从第二个元素开始把n-1个数据依次往前移的。


2.因为是n-1个元素,所以内层循环,我们的范围是[0,sz-1)===》也就是[0,sz-2];这样才是n-1个数据;如果这里我们取值范围写成[0,sz)===》也就是[0,sz-1];那么arr[j+1],也就是arr[sz]就会造成越界访问;毕竟下标是从0开始的,是[0,sz-1]取不到sz。


对于右旋:我们把第最后一个元素取出来,用tmp存起来===》tmp=arr[sz-1];然后在从后面倒数第二个元素依次往后移,下标是依次+1的,所以是arr[j+1]=arr[j];最后令第一个元素的位置arr[0]=tmp即可;这里我们也只强调两点:


1.只能从倒数第二个元素依次往后移,而不能从第一个元素往后移,因为这样同样会造成数据的覆盖!!!所以我们是从倒数第二个元素开始把n-1个数据依次往后移的。


2.同样我们内层循环的范围我们要把握好,我们是从倒数第二个元素开始的,它的下标是sz-2;所以范围应该是[sz-2,0];这里只要范围把握好,我相信就没什么问题了。


方法2:三步翻转法


2.1 解析:


所谓三步翻转,就是根据我们旋转(左旋或者右旋)的次数来作为分界面:


如果是左旋:从左边开始数,前面的[0,k-1]个元素翻转一次;后面的[k,sz-1]个元素翻转一次;最后整体的[0,sz-1]个元素在翻转一次;就能得到最终我们想要的结果;


如果是右旋:从右边开始数,前面的[0,sz-k-1]个元素翻转一次;后面的[sz-k,sz-1]个元素翻转一次;最后整体的[0,sz-1]个元素在翻转一次;就能得到最终我们想要的结果;


既然是三步翻转,每一次的步骤都是一样的,我们不妨封装一个函数,用的时候直接调用,避免写三次实现的代码,造成冗余。


时间复杂度为O(n),空间复杂度为O(1)


2.2 具体代码:

e778a777839f436592260be53b27a6f4.png

2.3 代码分析:


无论是左旋还是右旋,实际上调用的函数是一样的,就是传参不一样,所以就把它们写在一块了,读者要是测试,请先注释掉一个旋转方式,在测试。


对于一组数据1 2 3 4 5 6 7 8 9;大小为sz;旋转次数为k:


左旋:就是从左边开始数;传数组arr,传左边元素的下标,传右边元素的下标,以旋转次数k为分界线:


第一次传下标为0开始,k-1结束;


第二次传下标为k开始,sz-1结束;


第一次传下标为0开始,sz-1结束;


右旋:就是从右边开始数;传数组arr,传左边元素的下标,传右边元素的下标,以旋转次数k为分界线:


第一次传下标为0开始,sz-k-1结束;


第二次传下标为sz-k开始,sz-1结束;


第一次传下标为0开始,sz-1结束;


注意:有没有注意我们在第二步还判断取余一下了,为什么呢?

 

因为如果旋转的次数大于数据的个数,即:k>sz,就会造成越界访问,比如:左旋传参[k,sz-1],就是前面大后面小;比如右旋传参[sz-k,sz-1],sz-k这里就是一个负数;所以我们需要判断一下k与sz的关系,如果k>sz,就k=k%sz;为什么这样就可以?因为这是一个循环的过程,假如有9个数据,我们旋转1次和旋转10次的结果其实是一样的,所以我们不妨直接取模,即避免造成越界访问,又能减少旋转次数!!!



3c598a9849f04b348e299c77b25ce89d.jpg

相关文章
Leetcode226.翻转二叉树
Leetcode226.翻转二叉树
35 0
|
1月前
【LeetCode 29】226.反转二叉树
【LeetCode 29】226.反转二叉树
16 2
|
5月前
《剑指offer》--字符串左旋
《剑指offer》--字符串左旋
25 0
|
6月前
[LeetCode]—— 226——翻转二叉树
[LeetCode]—— 226——翻转二叉树
LeetCode | 226. 翻转二叉树
LeetCode | 226. 翻转二叉树
【Leetcode -110.平衡二叉树 -226.翻转二叉树】
【Leetcode -110.平衡二叉树 -226.翻转二叉树】
32 0
杨氏矩阵,字符串左旋,字符串旋转结果题目解析
杨氏矩阵,字符串左旋,字符串旋转结果题目解析
|
C++
C/C++每日一练(20230515) 区间和的个数、BST最近公共祖先、最接近元素
C/C++每日一练(20230515) 区间和的个数、BST最近公共祖先、最接近元素
94 0
leetcode236—二叉树的最近公共祖先(递归/深搜/理解)
leetcode236—二叉树的最近公共祖先(递归/深搜/理解)