189.轮转数组

题目描述题解1(使用额外的数组)(最简单)思路直接计算出每个元素最终应该待在哪里然后把它放到新数组的对应的位置代码classSolution{publicvoidrotate(int[]nums,intk){intnnums.length;int[]newArrnewint[n];for(inti0;in;i){newArr[(ik)%n]nums[i];}System.arraycopy(newArr,0,nums,0,n);}}System.arraycopy()方法详解题解2(环状替换)思路当我们把元素放到新位置时原来位置上的元素就会被覆盖。所以我们需要一个临时变量把原来的元素存起来然后再把存起来的元素放到它下一个该去的位置。一直重复这个过程直到所有的元素都被移动过代码classSolution{publicvoidrotate(int[]nums,intk){intnnums.length;// 如果 k 大于数组长度取余数即可因为移动 n 次等于没移动kk%n;if(k0)return;// count 用来记录已经被成功移动到最终位置的元素个数intcount0;// start 记录每一轮替换的起始位置for(intstart0;countn;start){intcurrentstart;// 当前正在处理的索引intprevnums[start];// 当前需要被移动的元素do{// 计算该元素应该去的新位置intnext(currentk)%n;// 暂存新位置上的原来元素inttempnums[next];// 将当前元素放到新位置nums[next]prev;// 准备处理刚才被替换出来的元素prevtemp;currentnext;// 成功移动了一个元素计数器加1count;}while(start!current);// 如果回到了当前这一轮的起点说明这一个环已经处理完了}}}题解3(数组翻转)思路代码classSolution{publicvoidrotate(int[]nums,intk){intnnums.length;// 如果 k 大于数组长度取余数即可kk%n;// 1. 翻转整个数组reverse(nums,0,n-1);// 2. 翻转前 k 个元素reverse(nums,0,k-1);// 3. 翻转剩余的 n - k 个元素reverse(nums,k,n-1);}// 辅助函数翻转数组 nums 中从 start 到 end包含边界的元素privatevoidreverse(int[]nums,intstart,intend){while(startend){inttempnums[start];nums[start]nums[end];nums[end]temp;start;end--;}}}