每日一道 LeetCode (42):旋轉(zhuǎn)數(shù)組
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉(cāng)庫(kù)
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：旋轉(zhuǎn)數(shù)組
題目來(lái)源：https://leetcode-cn.com/problems/rotate-array/
給定一個(gè)數(shù)組，將數(shù)組中的元素向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(shù)。
示例 1:
輸入:?[1,2,3,4,5,6,7]?和?k?=?3
輸出:?[5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn)?1?步:?[7,1,2,3,4,5,6]
向右旋轉(zhuǎn)?2?步:?[6,7,1,2,3,4,5]
向右旋轉(zhuǎn)?3?步:?[5,6,7,1,2,3,4]
示例?2:
輸入:?[-1,-100,3,99]?和?k?=?2
輸出:?[3,99,-1,-100]
解釋:?
向右旋轉(zhuǎn)?1?步:?[99,-1,-100,3]
向右旋轉(zhuǎn)?2?步:?[3,99,-1,-100]
說(shuō)明:
- 盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個(gè)問(wèn)題。
- 要求使用空間復(fù)雜度為 O(1) 的?原地?算法。
解題方案一：暴力法
暴力解題大家應(yīng)該都想得到，就是用兩個(gè)循環(huán)套起來(lái)，然后加一個(gè)中間變量來(lái)逐位替換位置。
public?void?rotate(int[]?nums,?int?k)?{
????int?temp,?previous;
????for?(int?i?=?0;?i?????????previous?=?nums[nums.length?-?1];
????????for?(int?j?=?0;?j?????????????temp?=?nums[j];
????????????nums[j]?=?previous;
????????????previous?=?temp;
????????}
????}
}
運(yùn)行時(shí)長(zhǎng)又超過(guò) 3 位數(shù)了，智商不行的人可能就單純的比較適合看答案。
解題方案二：使用額外的數(shù)組
這竟然都算一個(gè)解題方案，題目上不是說(shuō)要求使用空間復(fù)雜度為 O(1) 的?原地?算法么？
還帶這么玩的啊！
好吧好吧，你是答案，你說(shuō)了算，你說(shuō)啥都對(duì)。
能用額外數(shù)組這個(gè)題就很簡(jiǎn)單了，直接新建一個(gè)數(shù)組，然后把每個(gè)元素直接放在正確的位置上，最后放完以后再用這個(gè)數(shù)組對(duì)原數(shù)組挨個(gè)賦值。
public?void?rotate_1(int[]?nums,?int?k)?{
????int[]?a?=?new?int[nums.length];
????for?(int?i?=?0;?i?????????a[(i?+?k)?%?nums.length]?=?nums[i];
????}
????for?(int?i?=?0;?i?????????nums[i]?=?a[i];
????}
}
時(shí)間下降到 1ms ，有這么立竿見(jiàn)影的么，不過(guò)只超過(guò)了 57.17% 的人，說(shuō)明還有更快的方案，接著往下看答案。
解題方案三：使用環(huán)狀替換
這個(gè)方案有點(diǎn)意思，確實(shí)很難想，我就借用下官方的圖做下解釋：
這個(gè)圖是是畫了一個(gè)數(shù)組的移動(dòng)過(guò)程：
nums:?[1,?2,?3,?4,?5,?6]
k:?2
- 第一次移動(dòng)，從第一個(gè) 1 開始， 1 向后移動(dòng)兩位，到了 3 現(xiàn)在的位置，這時(shí)我們需要將 1 放到位置 3 上。
- 第二次移動(dòng)，因?yàn)?3 沒(méi)有了位置，我們接著計(jì)算 3 要移動(dòng)的位置，發(fā)現(xiàn) 3 要移動(dòng)到位置 5 上，那么我們把 3 移動(dòng)過(guò)去。
- 第三次移動(dòng)，現(xiàn)在是 5 沒(méi)有了位置，計(jì)算 5 需要的位置，在位置 1 上，而位置 1 現(xiàn)在正好空著，我們把 5 放進(jìn)去。
- 第四次移動(dòng)，開始畫紅線的部分，現(xiàn)在我們?cè)撘苿?dòng)位置 2 上的數(shù)字 2 了， 2 需要移動(dòng)到位置 4 上，我們把 2 移動(dòng)過(guò)去。
- ......
剩下的兩次移動(dòng)我就不寫了，和綠線部分是一致的。
當(dāng)整體移動(dòng)完成后，整個(gè)數(shù)組我們實(shí)際上只循環(huán)了一次，就完成了所有的移動(dòng)，這個(gè)時(shí)間復(fù)雜度是 O(n) 。
下面的代碼上注釋我已經(jīng)都寫好了，就不再解釋了：
public?void?rotate_2(int[]?nums,?int?k)?{
????//?先計(jì)算?k?，這個(gè)?k?為當(dāng)前需要移動(dòng)的位置，防止?k?超出數(shù)組長(zhǎng)度
????k?=?k?%?nums.length;
????//?初始化移動(dòng)的次數(shù)
????int?count?=?0;
????for?(int?start?=?0;?count?????????//?初始化當(dāng)前位置
????????int?current?=?start;
????????//?初始化要移動(dòng)的數(shù)
????????int?prev?=?nums[start];
????????do?{
????????????//?計(jì)算目標(biāo)要移動(dòng)的位置
????????????int?next?=?(current?+?k)?%?nums.length;
????????????//?定義中間變量
????????????int?tmp?=?nums[next];
????????????//?將要移動(dòng)的數(shù)字進(jìn)行賦值
????????????nums[next]?=?prev;
????????????//?這時(shí)，接著移動(dòng)剛才被擠掉位置的數(shù)
????????????prev?=?tmp;
????????????//?變化當(dāng)前的位置為剛才移動(dòng)的位置
????????????current?=?next;
????????????//?將操作次數(shù)?+1
????????????count++;
????????}?while?(start?!=?current);
????}
}
果然只遍歷一次耗時(shí)足夠低，不過(guò)時(shí)間復(fù)雜度為 O(n) 的還有下面的另一種思路。
解題方案四：使用反轉(zhuǎn)
這個(gè)操作也是相當(dāng)?shù)尿}，我是真的服。
答案上是這么解釋這個(gè)方案的：
這個(gè)方法基于這個(gè)事實(shí)：當(dāng)我們旋轉(zhuǎn)數(shù)組 k 次， k % n 個(gè)尾部元素會(huì)被移動(dòng)到頭部，剩下的元素會(huì)被向后移動(dòng)。
這句話看完我一臉懵，這是說(shuō)了個(gè)啥？然后接著往下看。
在這個(gè)方法中，我們首先將所有元素反轉(zhuǎn)。然后反轉(zhuǎn)前 k 個(gè)元素，再反轉(zhuǎn)后面 n - k 個(gè)元素，就能得到想要的結(jié)果。
這句話是看懂了，但是沒(méi)明白意思，直到看到了題目上舉的例子才看懂：
假設(shè) n=7 且 k=3 。
原始數(shù)組??????????????????:?1?2?3?4?5?6?7
反轉(zhuǎn)所有數(shù)字后?????????????:?7?6?5?4?3?2?1
反轉(zhuǎn)前?k?個(gè)數(shù)字后??????????:?5?6?7?4?3?2?1
反轉(zhuǎn)后?n-k?個(gè)數(shù)字后????????:?5?6?7?1?2?3?4?-->?結(jié)果
媽耶，這還是人能想出來(lái)的方案么？這題套路這么深還能算是一道簡(jiǎn)單題么？
方案有了實(shí)際上代碼就很簡(jiǎn)單了：
public?void?rotate_3(int[]?nums,?int?k)?{
????k?=?k?%?nums.length;
????reverse(nums,?0,?nums.length?-?1);
????reverse(nums,?0,?k?-?1);
????reverse(nums,?k,?nums.length?-?1);
}
private?void?reverse(int[]?nums,?int?start,?int?end)?{
????while?(start?????????int?temp?=?nums[start];
????????nums[start]?=?nums[end];
????????nums[end]?=?temp;
????????start++;
????????end--;
????}
}
這后面的簡(jiǎn)單題是越來(lái)越難了，嚴(yán)重感覺(jué)自己現(xiàn)在智商不夠用，看來(lái)是時(shí)候買點(diǎn)豬頭肉補(bǔ)補(bǔ)了。
