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

方法1：保存数组中最后一个数，将其他数向后移动一位，再将保存的数赋值给数组的第一个数。重复k次

rotate(int* nums,int numsSize,int k)
{
while(k--)
{
	int tmp =0;
	tmp=nums[numsSize-1];
	int end =0;
	for(end = numsSize-2;end>=0;end--)
	{
		nums[end+1]=nums[end];
	}
	nums[0]=tmp;
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

但如果测试用例的数组元素过多，则使用的时间会过长。O(k*n)

方法2：先将后k个数组元素逆置，再将前k个数组元素逆置，最后整体再逆置一次。

//Reverse函数用来进行逆置
void Reverse(int* nums, int left, int right)
{
	while (left < right)
	{
		int tmp = nums[left];
		nums[left] = nums[right];
		nums[right] = tmp;
		left++;
		right--;
	}
}
//当k大于数组的元素个数时，会发生内存越界。
//又因为当逆置的元素k等于数组的元素个数时，不变。所以当k>numsSize时，用k模numsSize，得到的值为实际需要移动的位置个数。
void rotate(int* nums, int numsSize, int k)
{
	if (k > numsSize)
	{
		k %= numsSize;
	}
	//第一次逆置后k个元素
	Reverse(nums, numsSize - k, numsSize - 1);
	//第二次逆置前K个元素
	Reverse(nums, 0, numsSize - k - 1);
	//第三次将整体再次逆置
	Reverse(nums, 0, numsSize - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

这个方法的空间复杂度、时间复杂度都为为O(1);