企业官网建设流程全解析

轮转数组

题目

三种思路

1、直接法

保存最后一个数据，前面数据挨个前移。循环k次。最后把end放到开头

while(k--){intend=nums[numssize-1];for(inti=numssize-1;i>0;i--){nums[i]=nums[i-1];}nums[0]=end;}

然而

回顾复杂度算法
时间复杂度：外层循环k次，内层循环i次。两个未知数相乘。O(n^2)
空间复杂度：创建了常数个变量。O(1)

2、新数组法

申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组
防止i+k越界，要模上numssize

intnewarr[100000]={0};for(inti=0;i<numssize;i++){newarr[(i+k)%numssize]=nums[i];}for(inti=0;i<numssize;i++){nums[i]=newarr[i];}此时的时间复杂度：O(n)，空间复杂度：O(n)。时间换空间。

3、原地法

前n-k个逆置——后k个逆置——整体逆置
此时的空间复杂度降到O(1)，时间复杂度不变。
但方法很有数学味道，比较难想。