轮转数组【补充】

本章概述

前情回顾
方法一
方法二
总结
彩蛋时刻！！！

前情回顾

点击：轮转数组。
在上面一章的《初阶数据结构【1】》里面，咱们通过轮转数组引出了算法复杂度的概念。咱们当时写的那个算法有点小问题，38个测试用例通过了37个测试用例。原因：超出时间限制。通过时间和空间复杂度计算，咱们写的那个算法时间复杂度为O（n^2），空间复杂度O（1）。通过数学曲线图，我们发现这个算法的时间复杂度不是很好。平台显示咱们超出时间限制，那么咱就降低时间复杂度。下面展示一些个人的方法（供大家参考），大家也可以自己想个更好的算法。

方法一

空间换取时间：之前的时间算法复杂度为O（n^2），超出时间限制。我们就降低时间复杂度，我们可以尝试降低到O(n)。思路：因为我们之前使用循环嵌套，所以时间复杂度就会出现n ^2。我们可以尝试不用循环嵌套，直接分离出一个循环。又或者，当我们一个循环不能够解决问题的时候，我们就用两个循环，而且这两个循环不是嵌套的，是等价的，时间复杂度为n+n=2n,O(n)。可以有效降低时间复杂度。我们可以再创建个新的数组，先把后（k）个元素都给转移到新数组的前面，再把剩下（numsSize-k）的元素转移到新数组的后面。最后，我们再把新数组的元素全部转移到之前的数组。如逻辑图所示：
我们理清了思路，那么我们就来写代码，进行代码展示：

void rotate(int* nums, int numsSize, int k) {int newarr[numsSize];for(int i=0;i<numsSize;i++){newarr[(k+i)%numsSize]=nums[i];}for(int i=0;i<numsSize;i++){nums[i]=newarr[i];}
}

结果运行图：在这里插入图片描述
这次的算法通过了。我们来计算一下这个程序的时间和空间复杂度，时间复杂度：O(n),空间复杂度(因为我们创建个新数组，空间大小和老数组一样，所以元素个数为numsSize,即空间复杂度为n)O(n)。我们发现。时间复杂度降低了，空间复杂度升高了，只要空间占用的不是特离谱，就不会出现错误（因为本身空间我们就不怎么在乎）。这就是拿空间来换取时间方法。

方法二

内部自换：思路：我们先把（numsSize-k）个元素前后交换数值，再把后（k）个元素前后交换数值。最后，我们再整体把这个数组的前后元素交换数值。注意：我们都是在同一个数组上交换数值。如图所示的逻辑图：
进行代码展示：

void reserve(int*num,int begin,int end)
{while(begin<end){int temp=num[begin];num[begin]=num[end];num[end]=temp;begin++;end--;}
}
void rotate(int* nums, int numsSize, int k) 
{reserve(nums,0,numsSize-k-1);reserve(nums,numsSize-k,numsSize-1);reserve(nums,0,numsSize-1);
}

结果运行图：在这里插入图片描述
我们有一个测试用例没通过，就是当这个数组的元素个数为1的时候，且还要轮转2次。那么，我们的reserve（）函数里面的参数就会出现负值，就会越界访问（下标值为负数的数组访问的方式咱们前面讲过）。这个函数本身没有什么问题，我们只需要处理一下k的取值就能解决问题——k%=numsSize;就能解决问题，进行代码展示：

void reserve(int*num,int begin,int end)
{while(begin<end){int temp=num[begin];num[begin]=num[end];num[end]=temp;begin++;end--;}
}
void rotate(int* nums, int numsSize, int k) 
{k%=numsSize;reserve(nums,0,numsSize-k-1);reserve(nums,numsSize-k,numsSize-1);reserve(nums,0,numsSize-1);
}

结果运行图：在这里插入图片描述
我们来算一下这个算法的时间和空间复杂度，时间复杂度：O(n),空间复杂度：O（1）。所以，到目前为止，这个算法是最好的算法。

总结

核心思想：这个问题的核心思想就是，我们通过轮转的结果，我们可以整体思想去移动数组元素，不会像起始的那样，一个一个的轮转，最后还要加个循环嵌套，效率太低。我们直接一块一块的移动（就像方法2和方法3的思路），效率就会很多。解决一个问题可能会有很多的方法，这些方法中有的效率很高，有的效率就会很低。转移到算法题中，也是如此。当我们有时候需要增加空间复杂度的时候就要去增加，以降低时间复杂度。