189.轮转数组

题目描述

题解1(使用额外的数组)(最简单)

思路

直接计算出每个元素最终应该待在哪里，然后把它放到新数组的对应的位置

代码

classSolution{publicvoidrotate(int[]nums,intk){intn=nums.length;int[]newArr=newint[n];for(inti=0;i<n;++i){newArr[(i+k)%n]=nums[i];}System.arraycopy(newArr,0,nums,0,n);}}

System.arraycopy()方法详解

题解2(环状替换)

思路

当我们把元素放到新位置时，原来位置上的元素就会被覆盖。所以，我们需要一个临时变量把原来的元素存起来，然后再把存起来的元素放到它下一个该去的位置。一直重复这个过程，直到所有的元素都被移动过

代码

classSolution{publicvoidrotate(int[]nums,intk){intn=nums.length;// 如果 k 大于数组长度，取余数即可，因为移动 n 次等于没移动k=k%n;if(k==0)return;// count 用来记录已经被成功移动到最终位置的元素个数intcount=0;// start 记录每一轮替换的起始位置for(intstart=0;count<n;start++){intcurrent=start;// 当前正在处理的索引intprev=nums[start];// 当前需要被移动的元素do{// 计算该元素应该去的新位置intnext=(current+k)%n;// 暂存新位置上的原来元素inttemp=nums[next];// 将当前元素放到新位置nums[next]=prev;// 准备处理刚才被替换出来的元素prev=temp;current=next;// 成功移动了一个元素，计数器加1count++;}while(start!=current);// 如果回到了当前这一轮的起点，说明这一个环已经处理完了}}}

题解3(数组翻转)

思路

代码

classSolution{publicvoidrotate(int[]nums,intk){intn=nums.length;// 如果 k 大于数组长度，取余数即可k=k%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(start<end){inttemp=nums[start];nums[start]=nums[end];nums[end]=temp;start++;end--;}}}