题目描述
解题思路
- 思路1
再次创建一个同等的大小的数组a，把原数组后k个位置的元素拷贝a数组的前k个位置。然后原数组剩下的元素拷贝在a数组剩余的位置。
最后把a数组全部的元素再次拷贝到原数组中。
时间复杂度O(n),空间复杂度O(n)
- 思路2
三步逆序（就是一个规律）
第一步：把后k个逆序
第二步：把剩下的逆序
第三步：全部逆序
时间复杂度O(n),空间复杂度O(1)
代码
思路1代码
void rotate(int* nums, int numsSize, int k){ k%=numsSize;//保证轮转数小于数组长度 int* a=(int*)malloc(numsSize*sizeof(int)); if(a==NULL) return; int i=0,j=0; for(i=numsSize-k;i<numsSize;i++) { a[j++]=nums[i]; } for(i=0;i<numsSize-k;i++) { a[j++]=nums[i]; } for(i=0;i<numsSize;i++) { nums[i]=a[i]; } free(a); a=NULL; }
思路2代码
void reverse(int* s1,int* s2) { int temp=0; while(s1<s2) { temp=*s1; *s1=*s2; *s2=temp; s1++; s2--; } } void rotate(int* nums, int numsSize, int k){ k%=numsSize; reverse(nums+numsSize-k,nums+numsSize-1); reverse(nums,nums+numsSize-k-1); reverse(nums,nums+numsSize-1); }
