萬網(wǎng)的怎么做網(wǎng)站地圖深圳seo優(yōu)化方案
題目鏈接: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);}