轮转数组-三次逆置

题目

给定一个整数数组 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++)
    {
    	//数组最后一个元素储存到val
        int 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要小于numsSize
    k %= 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;
    }
}

注：

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);
}