信念:解题的时候一定不要害怕自己想不出来,一定要相信自己,理解能力不好,多花点时间。多坚持一会,会豁然开朗的。
我的思考的过程:简直就是不断碰壁的过程,在想到这个解法之前我自己都无数次失败了。从早上起来7点半左右,到完成这个题目用了我两个小时。
思想:一旦在思考的过程中对问题有了进一步的认识,可以再往深的方面去思考
最开始的思路:
1.时间是昨天晚上,花了3个小时,一直在琢磨。可能是太笨了的原因,写个双重for循环来解决问题都很费脑子。
对应的代码如下
ps:代码很简单,但是算法的时间复杂度没达到要求,所以就出来了下面这个解题的过程
思路:就是每次把最后面的m个元素一个一个的往前面移动,一直移动到最开始的位置。
最后的思路:
1.我们经过不断的测试,通过例子进行演算,最终发现当m>=1时,无论m的取值是多少,我们需要反转的次数最少都是n-1.所以我们可以写一个for循环来表示。
for(int x = 0;x<n-1;x++)//这里循环的次数一定不要写多了,或者是写少了 { int tmp = a[i];//这里就直结把对应 的i,j坐标的元素的值给交换 a[i] = a[j]; a[j] = tmp; i = (i+m)%n; if(j==i) //如果要交换的两个下标相同的时候,说明此时右边的需要往后面移动一个单位 { i = (j+m)%n+1; j++; x++; } }
1.先把最后的m个元素的第一个移动到第一位;然后原来的第一位,就会移动成原来的m个元素的第一个。(为了方便以后的说明,不妨设这个最后m个元素的第一个元素对应的位置为中间的歇点。歇点可能会移动,也可能不会移动,具体是否移动下面会说明)
2.然后我们把原来的第一个元素的再后面的m个元素再找出来。(为了方便以后的说明,不妨设这个元素对应的后面的m个元素的点称为后点)
i = (i+m)%n; //后点的坐标移动的过程
3.我们要把此时歇点的数和后点的数进行交换。
int tmp = a[i];//这里就直结把对应 的i,j坐标的元素的值给交换 a[i] = a[j]; a[j] = tmp;
4.当后点和歇点没有重合的时候,我们就重复上述的循环,否则,我们就需要进行移动原来最开时的起点,以及歇点。
if(j==i) //如果要交换的两个下标相同的时候,说明此时右边的需要往后面移动一个单位 { i = (j+m)%n+1; j++; x++; } }
最后完整的代码分析
class Solution { public: /** * 旋转数组 * @param n int整型 数组长度 * @param m int整型 右移距离 * @param a int整型vector 给定数组 * @return int整型vector */ vector solve(int n, int m, vector& a) { // write code here m = m%n;//把m的值先和n去取余,把不用反转的情况都在if里面都作用了 if(m==0||n==1) { return a;//不用反转的时候,直接返回原来的a容器 } else{ int j = n-m; //把要反转的数组元素歇点的坐标 int i = 0;//把要反转的元素的左边的元素的下标找出来,从第一个开始 for(int x = 0;x<n-1;x++)//这里循环的次数一定不要写多了,或者是写少了 { int tmp = a[i];//这里就直结把对应 的i,j坐标的元素的值给交换 a[i] = a[j]; a[j] = tmp; i = (i+m)%n; //第一个后点,依次都会有后点 if(j==i) //如果要交换的两个下标相同的时候,说明此时右边的需要往后面移动一个单位 { i = (j+m)%n+1; j++; x++; } } return a; } } };