leetcode刷题之轮转数组的三大解法及对比

方法1：暴力逆置

//轮转k个位置，就是说明每个元素都平均向后移动了K次，总共移动次数等于元素个数*k

//解法1，设数组元素为1,2,3,4,5，当k为3时，5个元素移动1次变成：5，1,2,3,4；移动第2次变成：4,5,1,2,3
//移动第3次变成：3,4,5,1,2，即移动一次，相当于所有数组元素都移动了一次，总移动了5次；移动第二次，相当于所有数组元素移动了一次，加上前一次移动的，总移动10次；移动第三次，相当于所有数组元素移动了一次，加上前一次移动的，总移动15次，得出总的循环中执行次数等于移动次数等于kn,即时间复杂度为o(kn)=o(n)

//当k远小于n时，比如k是常数，那么k可以省略，时间复杂度变为O(n);当k接近n时，比如k=(n-1),时间复杂度变为
//o(（n-1）*n),(n-1)*n==n方减n,而大O不关心具体值，只关心估算，所以当n为1000000时，平方为 10000
0000,n可以忽略不计，所以大o里面留下了（n方），时间复杂度为o（n的平方）（，执行次数n越大，效率越低）

//当k等于n时，或者说k%n=0,那么就相当于1次也没轮转就解决了问题，n越大，轮转次数认为0，效率不变，因为k%n==0,时间复杂度为o(1)

现在用的算法最坏情况达到o(n方)，最好情况o(1),极其不稳定，到达o(n方时)，效率非常低下，具体代码如下

k = k % numsSize;
//当k<numsSize,例如3<7;则k=3%7=3,跟题目要求的三一样，接着往下交换；k>numsSize,10>7,则k=10%7=3，
也跟题目要求的三一样；
//接着往下交换；只有特殊情况，k==numsSize, 7==7时，可以不交换，直接提前退出程序
if (k == numsSize)
{
return;
}
int i = 0;
int j = 0;
int N = numsSize – 1;//N是数组最后一个元素的下标
for (i = 0; i < k; i++)
{
int num = nums[N];
for (j = N – 1; j >= 0; j–)//要想从前往后赋值并保证数据最后完整，则要从倒数第二个下标开始，倒数第二个下标
赋给最后一个下标值里的数据，接着倒数第三个下标赋给倒数第二个下标里的数据
{
nums[j + 1] = nums[j];

}
nums[0] = num;
}

方法2：最优解法：三段逆置
void rotate(int* nums, int numsSize, int k)
{

//先逆转数组的全部元素，使数组完全倒过来，例如：1，2,3,4,5;第一段逆置结果：5，4,3,2,1；第二段逆转，
逆转数组的前k个位置；第三段逆转，逆转数组的后n-k个位置

第一段逆转的时间复杂度为o(n):逆转numsSize/n个数组元素；第二段逆转的时间复杂度为o(k):逆转数组前k个元素；第三段逆转的时间复杂度为o(n-k)，逆转数组后n-k个元素。把时间复杂度相加，得到o(n+k+n-k)=o(2n)=o(n),即解法2的效率远大于解法1

//先第一段逆转
k = k % numsSize;//这里让k去取余，有两个目的，①若k大于数组元素个数，则K对数组个数取余得到真正要逆转数组的次数
//②.若k==数组元素个数，则不需要逆转数组，直接返回
if (k == numsSize)
{
return;
}
//否则k大于numsSize或小于numsSize的情况都要三次逆转
int i = 0;
int N = numsSize – 1;//N是数组的最后一个下标
int left = 0;
int right = N;
while (left < right)
{
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right–;

}
left = 0;
right = k – 1;

//接着第二段逆转
//注意left，right出了循环的值不会消失，会保留循环里面计算变化而来的值，而是出了main函数，值才会消失，所以每次
//循环用left,right ,left，right必须更新，重新赋值，不能用旧值
while (left < right)
{
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right–;

}

//第三段逆转
left = k;
right = N;
while (left < right)
{
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right–;

}

方法3：数组拷贝
//旋转数组方法三：数组拷贝，用memcpy内存拷贝函数：第一个参数是目的地址，第二个参数是要拷贝的数据的首地址，第三个参数要拷贝多少个字节数

首先，创建一个新数组，用变长数组，那么空间复杂度（为解决问题所开辟的变量个数）就为o(n),时间复杂度执行拷贝3次o(k+n-k+n)=o(n)，解法三的时间复杂度和解法2一样是o(n),效率远高于解法1，但是解法三的空间复杂度比解法二大，消耗的空间更大一些，所以解法二是最优解法

//思路，创建新数组，将旧数组里的后k个元素（下标从n-k开始）先拷贝到新数组里面，然后将旧数组里的前n-k（下标从旧数
组首元素地址开始）个元素拷贝到新数组后面，最后将新数组的首地址开始把所有元素拷贝到旧数组里完成替换数组

k = k % numsSize;
if (k == numsSize)
{
return;
}
int emp[numsSize];
memcpy(emp, nums + (numsSize – k), sizeof(int) * k);
memcpy(emp + k, nums, sizeof(int) * (numsSize – k));
memcpy(nums, emp, sizeof(int) * numsSize);