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