题目描述
思路1
时间复杂度O(n^2)
循环K次将数组所有元素向后移动⼀位（代码不通过 ）
void rotate(int* nums, int numsSize, int k)
{while(k--){int end = nums[numsSize-1];for(int i = numsSize - 1;i > 0 ;i--){nums[i] = nums[i-1];}nums[0] = end;}
} 思路2：
空间复杂度 O(n)
申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中
void rotate(int* nums, int numsSize, int k)
{int newArr[numsSize];for (int i = 0; i < numsSize; ++i){newArr[(i + k) % numsSize] = nums[i];}for (int i = 0; i < numsSize; ++i){nums[i] = newArr[i];}
} 思路3：
空间复杂度 O(1)
• 前n-k个逆置： 4 3 2 1 5 6 7
• 后k个逆置 ： 4 3 2 1 7 6 5
• 整体逆置 ： 5 6 7 1 2 3 4
void reverse(int* nums, int left, int right)
{while(left<=right){//left和right的数据进行交换int tmp=nums[left];nums[left]=nums[right];nums[right]=tmp;left++;right--;}
} void rotate(int* nums, int numsSize, int k)
{k=k%numsSize;//前n-k个数据逆置reverse(nums,0,numsSize-k-1);//后k个数据逆置reverse(nums,numsSize-k,numsSize-1);//整体逆置reverse(nums,0,numsSize-1);}
