一、引例：数组向右轮转k个位置
题干
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
力扣OJ链接
https://leetcode.cn/problems/rotate-array/
二、题干解析
根据对“数组轮转”这一操作的不同理解，本题可以分为两种宏观思路。我们一种一种介绍。
1. 思路一：从“轮转”的过程分析
从示例中我们不难发现，本题“向右轮转”的每次操作都相同：将数组中最右（最后）一个元素取出，换成数组的第一个元素；而其它元素整体顺序不变。即可将“轮转k次”拆分为：
数组每次向右轮转1次，一共轮转了k次。
从这个角度出发，我们可将整个轮转的大过程看作是一个大循环，我们只需要搞清楚进行一次轮转做了哪些事，再循环k次，就能获得最终的结果。
轮转k次法
我们考虑直接在原数组上进行操作，对每一次“轮转”的过程进行拆解。
用nums表示数组，用numsSize表示数组的长度。
每轮转转1次时，可归纳出如下步骤：
- 取走数组中最后一个数（是nums[ numsSize-1 ] ，注意下标），暂时存放在变量tmp中；
- 从 0到（numsSize-2） 的每一个数都向后挪动一位，即 nums[end+1] = nums[end]，以此来空出首元素位置;
- 空下来的第一位存放原数组的最后一位，即tmp
- 以上这个过程循环 k 次，就是轮转k次后的结果
轮转k次法 图示
这种思路最直接，也最容易想到。基于以上思路，我们可以给出如下接口函数：
void rotate(int* nums，int numsSize， int k) { for(int i = 0; i < k; i++){ int tmp = nums[numsSize-1]; for (int end = numsSize-2; end >= 0; end--) { nums[end+1] = nums[end]; } nums[0] = tmp; } }
这种方式是可以实现的。但并不够好。
它的时间复杂度为O(N*K)，事实上该代码在leetcode中是跑不过的，因为效率实在太低：
因而我们考虑，能否对现有的代码进行优化，提高代码的时间效率。
额外数组法
额外数组法的宏观思路与轮转k次法相同，均是通过拆解单次轮转的过程，再配上k次循环实现。但在细节操作上有所差异：额外数组法通过开辟一个临时数组temp，暂时存放要移出原数组的数。
这就像小和尚从山下提水到山顶的水缸里。轮转k次法相当于每次提水都只有小和尚一个人干，而且他每打满一桶水，就嘎嘎地从山底往山顶跑，卸完一桶水又跑下山再打一桶。一个人，每打完一桶水就要往返山顶和山脚，如果一共需要6桶水，那小和尚就要一个人跑6次，自然效率就不高了。
但小和尚很聪明，他对这个办法进行了改变：他又叫来了5个人，每个人提个桶帮他一块儿打水。这样，小和尚打完一桶水不必要立刻跑上山，等其余5个人都打完水了，再一块上山，一块儿把水卸进水缸里。这样一口气搬运，人手充足，6桶水只需要搬运一趟。这就是额外数组法。
具体操作如下：
开辟一个临时数组temp，暂时存放要移出原数组的那几个数。（相当于在原数组后面又拼了一段temp，移出去的数都存放到了temp里面）
然后再向右移动原数组内的数，一次移动 k 个单位（因为移出去了 k 个数）
最后把temp里面的元素归还到nums数组的前几个
额外数组法 图示
依次思路，可以给出如下代码：
void rotate(int* nums,int numsSize,int k) { //开辟一个新的数组 k = k % numsSize; //考虑到 k > numsSize 的情况 int* temp = (int*)malloc(k * sizeof (int)); //根据k的实际情况开辟新数组 //移出去的元素放进新的数组里面 int j = 0; for (int i = numsSize-k; i <= numsSize-1; i++) { temp[j] = nums[i]; j++; } //原数组各元素向右移动k位 for (int i = numsSize-1; i >= k; i--) { nums[i] = nums[i-k]; } //再把多出来的元素放到原数组首 for (int i = k-1;i>= 0; i--) { nums[i] = temp[i]; } }
注意
遇到数组，一定要注意控制下标！！！注意数组越界问题。强烈建议画图找规律（用“三板斧”分析），凭空想象的话，很容易想错，而且下标出现的问题一时不太好找，容易被忽略，最好从头开始就不要出错。
该算法的时间复杂度与空间复杂度均为O(N)。
注意 k %= numsSize这一语句：这是防止数组越界的关键步骤之一。当k大于数组长度时，进行取模运算。
2. 思路二：从“轮转”的结果分析
这就是我们今天要重点介绍的“三步转换法”。我们单独开一个目录板块来聊聊这个。
三、接上：三步转换法妙转数组
1. 从轮转结果分析思路
要达到数组轮转，有一个很厉害的思路：三步转换法。 我们直接进行介绍。
前面提到，这是一种从轮转的结果进行切入的思路：
这就是所谓的“整体逆序，内部有序”。当把①和②分别看作两块整体元素时，①和②相对于原数组而言是逆序的。而当①和②分别看作一个单独的数组时，它们的内部又是有序的。注意，这里说的“有序”“逆序”是和原数组相比，顺序是否发生变化（不是说升序降序的那个排序）。
结论
要达到向右轮转k次使数组“整体逆序，内部有序”的状态，只须三步：
先将后k个逆置，再将前（n-k）个逆置，最后整体逆置。
图解如下：
三步转换法 图示
同样，若以同样的规则向左轮转，依旧是三步：先将前k个逆置，再将后（n-k）个逆置，最后整体逆置。
三步转换法--向左轮转
以此我们可以进一步归纳总结，得出三步转换法结论：
若有轮转方向规定：向方向D轮转，就先将D方向的那k个逆置，再将剩下的（n-k）个元素逆置，最后整体逆置即可。（其实在数组整体逆置之前，先逆置内部哪部分是并不影响结果的，只要保证每个部分的内部都逆置过了即可。只是个人认为按方向分一分会比较好理解，不容易搞错。）
若无轮转方向规定（只要达到逆置的结果即可）：就不用考虑“先向哪个方向逆置”的问题（不用考虑方向），只需要挨个将所有块内部的元素逆置，最后整体逆置即可。逆置的过程可以封装成函数，遇到时调用即可。
言而总之，就一句话：三步逆置，将数组分块，块内元素先分别逆置，最后再整体逆置。
2. 代码实现
//将逆置操作封装为函数 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){ if(k > numsSize){ k %= numsSize; } reverse(nums,numsSize-k,numsSize-1); reverse(nums,0,numsSize-k-1); reverse(nums,0,numsSize-1); }
总结一下：
这个结论非常巧妙，我们最好记住。
该算法的空间复杂度为O(1)，时间复杂度为O(N)。
对于逆置函数：可以用交换位置的算法实现，并设置上界left和下界right，实现在某一个区间内（left到right之间）进行逆置操作，用while( left双指针+区间划分类问题，对于该类题型，我们后续会慢慢讨论
由于逆置操作要进行多次且每次的逻辑步骤都一样，所以可以单独封装成函数来调用。
轮转数组问题：如何实现数组“整体逆序，内部有序”？“三步转换法”妙转数组 （二）+ https://developer.aliyun.com/article/1518481?spm=a2c6h.13148508.setting.14.73ba4f0er6UkSh
