【初阶数据结构与算法】复杂度分析练习之轮转数组(多种方法)

复杂度练习之轮转数组

题目链接：https://leetcode.cn/problems/rotate-array/description/
   为什么我们把这道题作为复杂度的练习题呢？是因为我们以后做题都会涉及到复杂度的计算，我们要保证我们写的程序不会超出题目的时间和空间的要求
   这道题就可以给我们一些启发，比如这道题有的方法复杂度过高，超出了题目要求的时间或者是空间限制，我们就需要计算我们方法的时间和空间复杂度找出问题，然后及时的换另一种方法，不死磕一个方法

方法1

   我们先来看看题目的介绍以及其中的第一个示例：

   题目的大致意思就是对数组进行右轮转操作，每轮转一次就会把最右边的元素放到最左边去，把其它所有元素向后移动一位，然后将这样的操作进行k次，这样一解释我们的第一个思路就出来了
   就是将数组中最后一个元素存起来，然后把数组中除了最后一个元素外的所有元素往后移动一位，然后我们把最后一个元素再放到数组的开头，也就是下标为0的位置，如图：

   上图演示的就是轮转一次的过程，我们只需要将这个过程循环k次即可，知道思路过后我们就来实现这个代码，首先每次循环我们需要将最后一个元素保存，这里就定义一个整型变量end来存储
   关键就是我们要将除了最后一个元素的所有元素都向后移动一位，我们可以使用memmove函数，但是我们为了方便观察它的时间和空间复杂度，就手写一下
   由于从第一个元素直接往后移动会导致第二个元素被覆盖，所以我们采用的方法是从最后一个要移动的元素开始移动，然后移动倒数第二个需要移动的元素，如下图：

   为了实现上图的效果，我们使用一个for循环，将i定位到下标为数组元素大小-2的位置，在上面例子中，数组元素大小为7，减2后就是5，也就是我们要移动的最后一个元素
   在第一次循环中，i = 5，我们要将下标为5的元素放在下标为6的位置上，然后我们让i减1，在第二次循环中，i = 4，我们就要将下标为4的元素放在下标为5的位置上，然后i再减1，最后循环这样的操作，直到i不再是有效的下标，代码如下：

 for (int i = numsSize - 2; i >= 0; i--)
 {
     nums[i + 1] = nums[i];
 }

   循环结束之后就说明我们的数组需要移动的元素已经移动完毕了，最后一步就是将我们保存的end放入下标为0的位置，到这里我们的代码就写完了，如下：

void rotate(int* nums, int numsSize, int k)
{
    while (k--)
    {
        int end = nums[numsSize - 1];
        for (int i = numsSize - 2; i >= 0; i--)
        {
            nums[i + 1] = nums[i];
        }
        nums[0] = end;
    }
}

   我们来运行自测一下看看代码有没有问题：

   可以看到自测通过了，我们提交代码试试：

   可以看到居然失败了，平台提示我们代码的运行时间超出了限制，这是为什么呢？我们来计算一下我们这种方法的时间复杂度
   我们这种方法有两层循环，其中外层while循环的执行次数属于未知数，会运行k次，k可以非常大，内层的for循环的执行次数要看数组的元素个数，也属于未知数，会执行n次，所以最后总结一下，整个代码的时间复杂度是O( N^2 )的级别，这个时间复杂度是非常糟糕的，所以导致了我们的代码超出了时间限制
   在计算时间复杂度之后，我们顺便来计算一下这个代码的空间复杂度，可以看到我们创建的变量个数都是有限个，所以这个代码的空间复杂度为O(1)
   通过分析方法1的时间复杂度，我们发现它的时间复杂度达到了O( N^2 )，导致代码超出了时间限制，所以方法1并不可行，接着让我们来学习其它方法

方法2

   方法1没有通过检测的原因就是时间复杂度太高了，那么我们能不能将复杂度降到O(N)呢？说不定那时就可以通过
   在上面的方法1中我们每轮转一次就要将数组中的元素一个一个往后挪动，导致时间复杂度超出限制，于是在方法2中我们对它进行一个小小的优化，我们可以创建一个新的数组来一次性存放要移动的数据
   比如我们要轮转k次，那么就要移动k个元素，我们可以把原数组中后k个元素移动到新数组的前k个位置上，把前n-k个元素移动到新数组中的后n-k的位置上，它们看起来是两步，但是实际上我们可以通过一个很巧妙的方法将这两步一起实现了，如下：

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

是不是有点难懂，我们来结合画图来解释一下：

   当i = 0时，nums(i+k)%numsSize = 3，刚好是新数组中的后n-k个元素中的第一个元素，所以当i = 0时，就把原数组中前k个元素中的第一个元素，放入了新数组中的后n-k个元素中的第一个元素的位置，如图：

   所以循环往复n-k次都是慢慢把原数组中前n-k个元素，移动到新数组中后n-k个位置上，如图：

   当i = 4时，nums(i+k)%numsSize = 0，刚好就是把原数组后面的元素放到了新数组的最前面，循环往复k次过后，就成功地把原数组中后k个元素移动到了新数组中前k个位置上，如图：

   这样就成功实现了将原数组中的元素轮转k次后，存放在新数组中，但是由于判题的时候是根据原数组nums来判断的，所以我们还要写一个循环将新数组中的数据拷贝回原数组中，如下：

for(int i = 0; i<numsSize; i++)
{
      nums[i] = newarr[i];
}

   完整代码为：

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

   随后我们运行一下代码发现没有问题，然后我们提交一下，如图：

   可以看到代码成功通过了，接着我们来分析一下这段代码的时间复杂度和空间复杂度，我们使用了两个for循环，但是是并列而不是嵌套的关系，所以时间复杂度为O(N)，比上一个方法优化了很多
   接着我们来看空间复杂度，我们创建了一个和原数组相同大小的数组，所以空间复杂度就是O(N)，那么我们有没有什么方法再优化一下，使得时间复杂度保持O(N)，但是空间复杂度降到O(1)呢？这就是我们要介绍的方法3

方法3

   方法3也不墨迹了，我们直接给出方法，因为不太能想到，我们以前没见过没关系，只要以后会做就可以了，这个方法有三步，首先逆置前n-k个元素，然后逆置后k个元素，最后将整个数组整体逆置一次，如图：

   所以我们只需要写出一个实现逆置的函数，然后调用三次就可以了，关键在于如何逆置，其实很简单，就是将要逆置的元素中前面的元素和后面的元素交换位置，如图：

   接着我们就来写这个逆置方法，函数名就叫reserve，我们需要的参数就是数组nums，以及begin和end，begin和end就是我们要逆置的元素的开头和结尾的下标
   实现方法就是上图画出的样子，让begin和end位置的数据交换，然后begin往后走，end往前走，继续交换，直到begin>end，所以我们写一个循环，循环条件就是begin<end，那么begin会不会和end相等呢？
   如果我们要逆置的元素的个数为奇数，是有可能相等的，相等的时候它们指向同一个元素，自然不需要做交换，如下图：

   现在知道了原理，实现这个函数就非常简单了，如下：

void reserve(int* nums, int begin, int end)
{
    while( begin < end )
    {
        int tmp = nums[begin];
        nums[begin] = nums[end];
        nums[end] = tmp;
        begin++, end--;
    }
}

   实现完这个代码之后我们就可以使用了，先让前n-k个元素逆置，如下：

    reserve(nums, 0, numsSize-k-1);

   接着让后k个元素逆置，如下：

    reserve(nums, numsSize-k,numsSize-1);

   最后使得整个数组全部逆置，如下：

    reserve(nums, 0, numsSize-1);

   最后我们还要注意一点，就是我们的numsSize-k-1可能会没有意义，就是当这个数组被轮转的次数超过它本身的大小的时候，例如数组只有一个元素，但是要轮转2次，numsSize-k-1就是-2，没有意义了
   怎么解决呢？主要是我们要理解，如果轮转数组大小次，那么相当于没有轮转，还是以前的样子，所以我们可以使用下面的方法来避免数组轮转多个循环：

k = k % numsSize; 

   这样我们就可以保证数组不会多次循环轮转，比如元素大小是7个，轮转8次，那么前7次轮转会使得数组恢复原样，没有意义，最后轮转的1次才有意义，所以我们模上数组元素个数，使得轮转次数直接变成1，就让程序高效了
   同时也解决了numsSize-k-1没有意义的问题，如果数组只有一个元素，轮转两次，那么就让2模1，得到了0，numsSize-k-1=0，就可以使得上面我们的代码成立
接下来我们来看看完整题解：

void reserve(int* nums, int begin, int end)
{
    while( begin < end )
    {
        int tmp = nums[begin];
        nums[begin] = nums[end];
        nums[end] = tmp;
        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)

总结

最后我们来总结一下我们上面写的三个方法

1. 在方法1中，我们使用了两层循环嵌套，每轮转一次就要把n - 1个数据往后挪动一次，虽然空间复杂度为O(1)，但是时间复杂度到达了O(N^2)，不是很好，导致了最后超出了题目的时间限制
2. 在方法2中，我们创建了一个和原数组相同大小的新数组，然后把轮转后的数据存放进这个新数组，关键就是要理解newarr[(i+k)%numsSize] = nums[i]这条语句，最后再将轮转完后的新数组的数据重新放回原数组，它的时间复杂度为O(N)，空间复杂度为O(N)，已经可以通过题目，但是它的空间复杂度还是稍微有点高
3. 在最后的方法3中，我们实现了一个函数可以逆置数组中的元素，我们只需要调用这个函数三次就可以实现数组的轮转，第一次逆置前n-k个元素，第二次逆置后k个元素，最后将整个数组逆置就可以使得数组轮转k次，我们要注意的是要理解为什么要使用k%=numsSize这条语句
4. 最后的思考环节，这里我们的轮转是向右轮转，如果是向左轮转该怎么做呢？向左轮转和向右轮转的关系是什么呢？欢迎在评论区讨论

   那么今天的分享就到此结束啦，我们虽然整篇文章只讲了一道题，但是我们更加深入地理解了时间复杂度和空间复杂度的重要性，这是我们以后写程序需要时刻注意的
   如果有什么问题欢迎私信我，bye~