轮转数组问题：如何实现数组“整体逆序，内部有序”？“三步转换法”妙转数组（一）

一、引例：数组向右轮转k个位置

题干

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

力扣OJ链接

https://leetcode.cn/problems/rotate-array/

二、题干解析

根据对“数组轮转”这一操作的不同理解，本题可以分为两种宏观思路。我们一种一种介绍。

1. 思路一：从“轮转”的过程分析

从示例中我们不难发现，本题“向右轮转”的每次操作都相同：将数组中最右（最后）一个元素取出，换成数组的第一个元素；而其它元素整体顺序不变。即可将“轮转k次”拆分为：

数组每次向右轮转1次，一共轮转了k次。

从这个角度出发，我们可将整个轮转的大过程看作是一个大循环，我们只需要搞清楚进行一次轮转做了哪些事，再循环k次，就能获得最终的结果。

轮转k次法

我们考虑直接在原数组上进行操作，对每一次“轮转”的过程进行拆解。

用nums表示数组，用numsSize表示数组的长度。

每轮转转1次时，可归纳出如下步骤：

1. 取走数组中最后一个数（是nums[ numsSize-1 ] ，注意下标），暂时存放在变量tmp中；
2. 从 0到（numsSize-2） 的每一个数都向后挪动一位，即 nums[end+1] = nums[end]，以此来空出首元素位置;
3. 空下来的第一位存放原数组的最后一位，即tmp
4. 以上这个过程循环 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