轮转数组（超详细！）

前言：

小编在上一篇文章的时候拿过轮转数组作为例子来讲述复杂度，但是小编并没有给出这个题目的正确解答，既然读者朋友已经了解复杂度了（不了解也没关系，可以看小编上一篇·文章），下面，跟随小编的脚步开始进入此习题的讲解！

目录：

1.轮转数组的解法一

2.轮转数组的解法二

3.两种解法对应的完整代码

正文：

1.轮转数组的解法一

首先，小编先放上这个题的大概内容，防止一些读者朋友知不道这个题目是什么：

首先，我们知道如果时间复杂度是0（N ^ 2）的话，这个代码是通不过的，下面先来展示一下错误案例：

void rotate(int* nums, int numsSize, int k) {
    int i = 0,end = 0;
    while(k--)
    {
        end = nums[numsSize - 1];
        for(i = numsSize - 1 ; i > 0 ; i--)
        {
            nums[i] = nums[i - 1];
        }
        nums[0] = end;    //三天没敲代码了差点没忘干净
    }
}

上面代码小编在之前写过，上面就是时间复杂度是0（N ^ 2），所以没有通过，下面我们可以通过减少循环次数来对于这个代码进行修改（就比如我们不要进行循环的嵌套），此时小编先来讲述一下第一种解法，我们可以通过开辟一个新的数组来进行这个代码的书写，下面就是小编的大致思路：

首先，我们可以用malloc函数来创建一个新数组，下面是代码的呈现：

int* arr = (int*)malloc(numsSize * sizeof(int));  //开辟空间，创立一个数组

在我们开辟完新数组以后，很多读者朋友会有疑问，我们为什么要创立新的数组呢？其实，我们开辟这个新数组的作用，是把它当作中间商的，它是来存放我们数组进行轮换之后的数的，之后我们可以把轮转完后的新数组的内容在给予我们本来的数组，这样我们就可以减少时间复杂度了！下面我们先来说一下如何进行轮转操作：

首先，我们还是画一下轮转数的原理图，方便大家去理解：

上面便是轮转数组的原理，下面我们应该思考下，我们如何将旧数组的内容通过一种怎样的方式来传给新数组呢？这里小编将要给大家一个比较nb的算法了，这个算法真的，你看一眼就会觉的这个算法很妙，下面我们先给上代码：

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

很多读者朋友可能会很奇怪，为什么arr[]里面是这个内容，下面小编通过图文的方式进行解释 :

通过这个图文解释，我们可以看到进行这个算法的加持下，这个代码完美的实现了轮转操作，这里便展现了这个算法的nb之处，说实在的，小编第一次看到这个代码，就觉得这个代码很强大，能够写出这个代码的人，算法的能力肯定是很高的，我们将数组轮转以后的结果放到新数组以后，下面我们就可以进行循环赋值操作了，代码如下：

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

我们经过时间复杂度的计算以后，可以算出来这个代码的时间复杂度和空间复杂度都是0（N），此时这个代码经过运行是可以通过的，这个就是解法一，下面小编开始讲述解法二！

2.轮转数组的解法二

对于轮转数组，第二种解法思路就是通过空间复杂度来代替时间复杂度的思想来进行撰写，此时这个代码主要看空间复杂度从而忽略时间复杂度，这里小编先透露一下，此时的空间复杂度是O（1），下面小编将会解释这个代码如何进行撰写！

在讲述解法二之前，小编先考一下各位读者朋友，我们是否可以通过逆置的方法来对数组进行轮转？答案是肯定的，下面小编先来通过例子的方式，来给各位读者朋友来解释一下，我们如何通过逆置来进行轮转操作的。

首先，我们可以先将数组前n - k 个数进行逆置，下面我们通过前面的特例进行图文解释：

之后，我们再将后面k个元素进行逆置，下面是图文解释：

最后，我们将所有元素进行逆置操作：

这里我们会发现，这里我们成功的将数组进行轮转了，所以我们进行三步逆置操作可以进行轮转操作！所以依靠这个思想，我们可以展开对于解法二的书写：

首先，我们需要创建一个函数，这个函数可以进行逆置操作，此时函数内部应该放置三个变量，一个是数组名，一个表示开头，一个表示结尾，至于为什么这么设置，且听我娓娓道来：

首先，我们想要进行逆置操作的话，首先是要确定开头和末尾的数字的，之后我们可以通过设置中间量的方式，把开头和结尾两个数进行交换，之后开头++，结尾--，从而可以完成轮转操作，这里我们需要用到循环的知识，下面是代码的书写：

void jiaohuan(int * arr,int left,int right)
{
    while(left < right)
    {
        int tmp;
        tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        left++;
        right--;
    }

}

之后我们在进行函数调用操作即可完成这个代码：

void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize;
    jiaohuan(nums,0,numsSize - k - 1);
    jiaohuan(nums,numsSize - k,numsSize - 1);
    jiaohuan(nums,0,numsSize - 1);

}

以上便是解法二如何进行书写，此时我们巧用空间复杂度来代替时间复杂度，从而做到了这个代码的复杂度减小，可能很多读者朋友只想看到完整的代码，下面小编将要展示这个题目完整代码：

3.两种解法对应的完整代码

解法一：

void rotate(int* nums, int numsSize, int k) {
	int* arr = (int*)malloc(numsSize * sizeof(int));  //开辟空间，创立一个数组
	assert(arr);
	for (int i = 0; i < numsSize; i++)
	{
		arr[(i + k) % numsSize] = nums[i];
	}
	for (int i = 0; i < numsSize; i++)
	{
		nums[i] = arr[i];
	}
}

解法二：

void jiaohuan(int * arr,int left,int right)
{
    while(left < right)
    {
        int tmp;
        tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
        left++;
        right--;
    }

}

void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize;
    jiaohuan(nums,0,numsSize - k - 1);
    jiaohuan(nums,numsSize - k,numsSize - 1);
    jiaohuan(nums,0,numsSize - 1);

}

总结：

以上便是轮转数组的相关内容，这里不得不感慨算法的多样性，一个题目就可以撰写出好几个代码，各位读者朋友一定要好好的去理解，如果文章有错误，恳请在评论区指出，我们在下一篇文章见喽！