題目鏈接：189. 輪轉(zhuǎn)數(shù)組 - 力扣（LeetCode）

?思路一

我們可以在進(jìn)行每次輪轉(zhuǎn)的時(shí)候，先將數(shù)組的最后一個(gè)數(shù)據(jù)的值存儲(chǔ)起來，接著將數(shù)組中前n-1個(gè)數(shù)據(jù)依次向后移，最后將存儲(chǔ)起來的值賦給數(shù)組中的第一個(gè)數(shù)據(jù)。

先將數(shù)組中最后的一個(gè)元素的值存到變量tmp中，如下圖

接著將數(shù)組中前n-1個(gè)數(shù)據(jù)依次向后移，如下圖?

最后再將tmp中的值賦值給nums[0]，如下圖?

以上圖是表示一次輪轉(zhuǎn)的，如果還要輪轉(zhuǎn)，重復(fù)上面的操作。

代碼實(shí)現(xiàn)

public void rotate(int[] nums, int k) {for(int i=0;i<k;i++){int tmp=nums[nums.length-1];//將前n-1個(gè)元素向后移for(int j=nums.length-1;j>0;j--){nums[j]=nums[j-1];}nums[0]=tmp;}}

當(dāng)我們提交以上代碼時(shí)，會(huì)發(fā)現(xiàn)不成功。

思路是對(duì)的，但是上面代碼時(shí)間復(fù)雜度為O(kn)，太復(fù)雜了，超出了題目的時(shí)間限制。?

思路二

造成思路一時(shí)間復(fù)雜度太大的原因是：?思路一中有兩個(gè)循環(huán)，一個(gè)循環(huán)是數(shù)組右旋的次數(shù)，另一個(gè)循環(huán)要將數(shù)組中的元素全部遍歷一遍，這樣當(dāng)右旋次數(shù)足夠多，數(shù)組中的元素很多時(shí)，效率就很低了。

思路二是k次旋轉(zhuǎn)法。

下面以旋轉(zhuǎn)次數(shù)為3來講解，也就是k=3

先將數(shù)組全部旋轉(zhuǎn)一遍，如下圖

再以下標(biāo)為0為起始點(diǎn)和下標(biāo)為(k%nums.length)-1為終點(diǎn)來旋轉(zhuǎn)，如下圖

?最后以下標(biāo)為(K%數(shù)組長度）為起始點(diǎn)和以下標(biāo)為（數(shù)組長度-1）為終點(diǎn)來旋轉(zhuǎn)數(shù)組。

這樣就完成了數(shù)組的3次右旋。

代碼實(shí)現(xiàn)

public void reverse(int[] nums,int start,int end){while(start<end){int tmp=nums[start];nums[start]=nums[end];nums[end]=tmp;start++;end--;}}public void rotate(int[] nums, int k) {reverse(nums,0,nums.length-1);reverse(nums,0,(k%nums.length)-1);reverse(nums,k%nums.length,nums.length-1);}

思路三

我們可以創(chuàng)建一個(gè)新的數(shù)組，將原數(shù)組中的數(shù)據(jù)按照數(shù)組旋轉(zhuǎn)之后的的位置放置到新數(shù)組中對(duì)應(yīng)的位置。最后我們?cè)賹⑿聰?shù)組復(fù)制到原數(shù)組中就行了。

有一個(gè)公式：（(i+k)%數(shù)組的長度) 的值 是 原數(shù)組中下標(biāo)為i的數(shù)據(jù) 在 新數(shù)組中的位置。

其中i為原數(shù)組中數(shù)據(jù)的小標(biāo)，k為旋轉(zhuǎn)次數(shù)。?

理解公式：

假如數(shù)組向右旋轉(zhuǎn)k，也就是讓數(shù)組中的數(shù)據(jù)向右移動(dòng)k個(gè)位置，但是如果k大于數(shù)組長度，就會(huì)越界，所以我們要%數(shù)組的長度。因?yàn)槿绻D(zhuǎn)的次數(shù)超過數(shù)組的長度，也就是旋轉(zhuǎn)k次的效果和k減去數(shù)組的長度次的效果是一樣的。

代碼實(shí)現(xiàn)

public void rotate(int[] nums, int k) {int n=nums.length;//創(chuàng)建一個(gè)新數(shù)組jianint[] newNums=new int[n];//將原數(shù)組中的數(shù)據(jù)放到新數(shù)組中for(int i=0;i<n;i++){newNums[(i+k)%n]=nums[i];}//將新數(shù)組復(fù)制到原數(shù)組System.arraycopy(newNums,0,nums,0,n);}