題目連結(jié)：
題目意譯：
給定一陣列 num，往右旋轉(zhuǎn)該陣列 k 步，其中 k 為非負(fù)整數(shù)。
進(jìn)階：
試圖得出盡可能多的解答，這題存在至少 3 種相異的解法。
你可以 O(1) 額外空間原地（In-Place）做出這題嗎？
限制：
1 ≦ nums.length ≦ 2 × 10 ^ 4
保證 nums[i] 可以存在 32 有號(hào)整數(shù)裡。
k ≧ 0
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： nums = [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]
範(fàn)例 2：
輸入： nums = [-1,-100,3,99] ， k = 2
輸出： [3,99,-1,-100]
解釋：
往右轉(zhuǎn) 1 步： [99,-1,-100,3]
往右轉(zhuǎn) 2 步： [3,99,-1,-100]
解題思維：
首先，暴力法當(dāng)然可行。因?yàn)榭梢钥吹矫肯蛴倚D(zhuǎn) num.length 次就會(huì)回到原本的樣子。因此我們可以將 k 值除以 num.length 取餘數(shù)，作為新的 k 值。接著就是一個(gè)一個(gè)的交換之步驟，全部交換後才算一次，然後要跑 k 次。
不介意使用額外空間的話，可以使用額外的陣列。對(duì)於每個(gè)位置 i 的元素放到 i + k （超過(guò)範(fàn)圍要繞回到開(kāi)頭繼續(xù)算）的位置。然後再將新陣列的內(nèi)容複製回來(lái)即可。
當(dāng)然，有 O(num.length) 時(shí)間複雜度又是 O(1) 空間複雜度的做法，如下：
舉例來(lái)說(shuō)，現(xiàn)有 6 個(gè)數(shù) 5 4 8 7 6 3 ，位置索引值為 0 1 2 3 4 5，要往右旋轉(zhuǎn) 2 步。
我們將數(shù)字分為恰好 2 組，一組為索引值 0 2 4 ，另一組為 1 3 5。可以看到每一組中的相鄰數(shù)字差距剛好為 2 。
將位置 i 作為基準(zhǔn)。第一次先跟位置 i + k 的元素交換，所以 i 跑到了應(yīng)該要去的位置即 i + k，而現(xiàn)在位置 i 的元素是原本的位置 i + k 的元素；接著第二次再跟位置 i + 2k 的交換……以此類推。直到繞回來(lái)到位置 i 時(shí)，即停止步驟。而這就是每一「組」數(shù)字要做的事。
將每一組各自跑完上面的步驟之後即完成要求。而對(duì)於一般情況，數(shù)字分組的組數(shù) ＝ GCD(num.length, k) ，其中 GCD 代表最大公因數(shù)。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
