轮转数组-三次逆置

题目

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

void rotate(int* nums, int numsSize, int k){}

示例：
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

思路1

如示例所示般，一个一个地转。
先将数组最后一个元素储存到val，再将前numsSize-1个元素向后搬，最后把val的值赋给nums[0]，就实现了最后一个元素放到数组开头。循环k次，就完成了轮转。

此方法效率较低，可能会超时。

void rotate(int* nums, int numsSize, int k) {//循环k次for (int i=0; i<k; i++){//数组最后一个元素储存到valint val = nums[numsSize-1];//前numsSize-1个元素向后搬for (int j=numsSize-1; j>0; j--){nums[j] = nums[j-1];}//把val的值赋给nums[0]nums[0] = val;}
}

思路2

三次逆置

示例：
输入: nums = [1,2,3,4,5,6,7], k = 3
4 3 2 1 5 6 7 前numsSize-k个逆置
4 3 2 1 7 6 5 后k个逆置
5 6 7 1 2 3 4 整体逆置

void rotate(int* nums, int numsSize, int k){//k要小于numsSizek %= numsSize;//前numsSize-k个逆置for (int i=0; i<(numsSize-k)/2; i++){int temp = nums[i];nums[i] = nums[numsSize-k-1-i];nums[numsSize-k-1-i] = temp;}//后k个逆置for (int i=0; i<k/2; i++){int temp = nums[numsSize-k+i];nums[numsSize-k+i] = nums[numsSize-1-i];nums[numsSize-1-i] = temp;}//整体逆置for (int i=0; i<numsSize/2; i++){int temp = nums[i];nums[i] = nums[numsSize-1-i];nums[numsSize-1-i] = temp;}
}

时间复杂度O(n)；空间复杂度O(1)。
注：

1. 次数k如果等于0，逆置0次为没有逆置，数组不变，没有运算的必要。
2. k要小于musSize，会有k大于等于numsSize的情况。例如：nums={-1}，k=2。如果k=numsSize的话，逆置结果为原来的数组，不变，没有计算的必要。使用求余%操作使得k的取值范围为0~numsSize-1。
3. for循环里，循环条件里需要 /2，如果时下标0~numsSize的元素逆置，当i=0时，nums[0]和nums[numsSize-1]交换；当i=numsSize-1时，nums[numsSize-1]和nums[0]交换，交换两次，结果不变。

代码改进

将交换部分封装函数reverse

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);reverse(nums, numsSize-k, numsSize-1);reverse(nums, 0, numsSize-1);
}

//3.空间换时间

开辟新空间tmp储存逆置后的数组，分别将前numsSize-k个和后k个放到tmp，因为nums是一级指针，所以直接nums=tmp没有用，要通过memcpy函数将tmp(逆置后的数组)复制给原数组

void rotate(int* nums, int numsSize, int k)
{k %= numsSize;int* tmp = (int*)malloc(sizeof(int)*numsSize);//逆置memcpy(tmp, nums+numsSize-k, sizeof(int)*k);memcpy(tmp+k, nums, sizeof(int)*(numsSize-k));//复制给原数组memcpy(nums, tmp, sizeof(int)*numsSize);//释放空间free(tmp);tmp = NULL;
}

时间复杂度O(n); 空间复杂度O(n)