启航数据结构算法之绮旅，漫步C++智慧之道——LeetCode题海探幽：轮转数组之多元策略演绎

人无完人，持之以恒，方能见真我！！！
共同进步！！

文章目录

• 复杂度练习之轮转数组
• • 方法1
  • 方法2
  • 方法3
• 总结

复杂度练习之轮转数组

题目链接：轮转数组

为什么我们把这道题作为复杂度的练习题呢？是因为我们以后做题都会涉及到复杂度的计算，我们要保证我们写的程序不会超出题目的时间和空间的要求

这道题就可以给我们一些启发，比如这道题有的方法复杂度过高，超出了题目要求的时间或者是空间限制，我们就需要计算我们方法的时间和空间复杂度找出问题，然后就可以使用另一种解法

方法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];
 }

变量 k 的循环结束之后就说明元素的移动完毕了，最后一步让 nums[0] = end 就可以了

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;//在0下标处赋值
    }
}

我们来提交一下看看有没有问题：

可以看到LeetCode提示超出时间限制,那我们就来算一下时间复杂度

我们这种方法有两层循环，因为k是变量，其外层while循环的执行次数属于未知数，会运行k次，k可以非常大，内层的for循环的执行次数要看数组的元素个数，也属于未知数，会执行n次，所以最后总结一下，整个代码的时间复杂度是O( N^2 )的级别，这是相当的差的时间复杂度，所以导致了我们的代码超出了时间限制

在计算时间复杂度之后，我们顺便来计算一下这个代码的空间复杂度，可以看到我们创建的变量个数都是有限个，所以这个代码的空间复杂度为O(1)

通过分析方法1的时间复杂度，我们发现它的时间复杂度达到了O( N^2 )，导致代码超出了时间限制，所以这种方法我是不推荐的，因为这样写出来实在是太矬了，那我们就继续向下看看更好的一些想法

方法2

在上面的方法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时，(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精妙绝伦，是我们大部分人很难想到的，这个方法有三步，首先逆置前n-k个元素，然后逆置后k个元素，最后将整个数组整体逆置一次，如图：

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

接着我们就来写这个逆置函数 reserve ，我们需要的参数就是数组nums，以及begin和end

由上面的图不难看出，让begin和end位置的数据交换，然后begin往后走，end往前走，继续交换，直到begin > end，所以我们写一个循环，循环条件就是begin<end，如果元素为奇数个也不影响，begin 和 end相等指向同一个元素，自然不需要交换

通过一系列的画图分析，我们就可以把 reverse 写出来了

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

然后把 reverse 复用三次就可以了

    reserve(nums, 0, numsSize-k-1);//先让前n-k个元素逆置
    reserve(nums, numsSize-k,numsSize-1);//接着让后k个元素逆置
    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 reverse(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;
    reverse(nums,0,numsSize - k -1);//前numSize-k个
    reverse(nums,numsSize - k,numsSize - 1);//后k个
    reverse(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、虽然我们这道题时向右轮转，但是如果要是向左轮转，这时候又应该怎么做呢

OK，今天我们关于轮转数组这道题就讲到这里，欢迎大家私信博主哦~~