1. 題目描述
題目鏈接: 輪轉(zhuǎn)數(shù)組
給定一個(gè)整數(shù)數(shù)組 nums，將數(shù)組中的元素向右輪轉(zhuǎn) k **個(gè)位置，其中 k **是非負(fù)數(shù)。
示例 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]
示例 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]
2. 使用額外的數(shù)組
一種比較簡(jiǎn)單的方法，是創(chuàng)建一個(gè)新的數(shù)組，將原數(shù)組的元素按照旋轉(zhuǎn)后的位置依次放入新數(shù)組中。這種方法需要O(n)的額外空間，其中n是數(shù)組的長(zhǎng)度。
下面是一個(gè)詳細(xì)說(shuō)明和示意圖，演示如何使用額外的新數(shù)組來(lái)實(shí)現(xiàn)數(shù)組向右旋轉(zhuǎn)。假設(shè)我們有一個(gè)數(shù)組 nums = [1, 2, 3, 4, 5, 6, 7]，要將其向右旋轉(zhuǎn)3個(gè)位置（k=3），我們將創(chuàng)建一個(gè)新數(shù)組 new_nums，并按照旋轉(zhuǎn)后的位置依次將元素從原數(shù)組中放入新數(shù)組中。
創(chuàng)建一個(gè)新數(shù)組 new_nums，與原數(shù)組 nums 同樣大小，初始都為0：
原數(shù)組： [1, 2, 3, 4, 5, 6, 7]
新數(shù)組： [0, 0, 0, 0, 0, 0, 0]
遍歷原數(shù)組 nums 中的每個(gè)元素，將元素按照旋轉(zhuǎn)后的位置放入新數(shù)組 new_nums 中。為了確定每個(gè)元素的新位置，我們可以使用以下公式：新位置 = (當(dāng)前位置 + k) % 數(shù)組長(zhǎng)度。 當(dāng)前例子中，k=3，數(shù)組長(zhǎng)度為7。
開(kāi)始遍歷，第一個(gè)元素1的新位置為 (0 + 3) % 7 = 3，所以將1放入新數(shù)組的第3個(gè)位置：
原數(shù)組： [1, 2, 3, 4, 5, 6, 7]
新數(shù)組： [0, 0, 0, 1, 0, 0, 0]
第二個(gè)元素2的新位置為 (1 + 3) % 7 = 4，所以將2放入新數(shù)組的第4個(gè)位置：
原數(shù)組： [1, 2, 3, 4, 5, 6, 7]
新數(shù)組： [0, 0, 0, 1, 2, 0, 0]
繼續(xù)這個(gè)過(guò)程，將所有元素按照新位置放入新數(shù)組：
原數(shù)組： [1, 2, 3, 4, 5, 6, 7]
新數(shù)組： [5, 6, 7, 1, 2, 3, 4]
最終旋轉(zhuǎn)完成，將新數(shù)組 new_nums 的數(shù)據(jù)拷貝到原數(shù)組當(dāng)中即可:
原數(shù)組： [5, 6, 7, 1, 2, 3, 4]
新數(shù)組： [5, 6, 7, 1, 2, 3, 4]
這個(gè)過(guò)程中，我們創(chuàng)建了一個(gè)新數(shù)組，并根據(jù)旋轉(zhuǎn)后的位置依次將原數(shù)組的元素放入新數(shù)組。這種方法需要O(n)的額外空間，其中n是數(shù)組的長(zhǎng)度
3. 數(shù)組翻轉(zhuǎn)
這道題是將數(shù)組中的元素從一處移動(dòng)到另一處，通?？梢钥紤]反轉(zhuǎn)這一操作，因?yàn)榉崔D(zhuǎn)是可逆的。在向右旋轉(zhuǎn)問(wèn)題中，我們可以將旋轉(zhuǎn)操作看作是將數(shù)組分為兩部分，然后將這兩部分交換位置。反轉(zhuǎn)這兩個(gè)部分的順序就可以實(shí)現(xiàn)向右旋轉(zhuǎn)。
這里通過(guò)數(shù)組翻轉(zhuǎn)來(lái)實(shí)現(xiàn)向右旋轉(zhuǎn)時(shí)，可以通過(guò)三次翻轉(zhuǎn)操作來(lái)完成。這個(gè)方法不需要額外的數(shù)組空間，只需要在原數(shù)組上進(jìn)行操作。下面詳細(xì)說(shuō)明其中的過(guò)程，假設(shè)有一個(gè)數(shù)組 nums = [1, 2, 3, 4, 5, 6, 7]，要將其向右旋轉(zhuǎn)3個(gè)位置(k=3):
首先，將整個(gè)數(shù)組翻轉(zhuǎn)。這將把數(shù)組的最后k個(gè)元素移到數(shù)組的前面:
原數(shù)組： [1, 2, 3, 4, 5, 6, 7]
翻轉(zhuǎn)后： [7, 6, 5, 4, 3, 2, 1]
此時(shí)，數(shù)組的前3個(gè)元素是原數(shù)組的最后3個(gè)元素，接下來(lái)，翻轉(zhuǎn)前k個(gè)元素。這將把原數(shù)組的最后k個(gè)元素移動(dòng)到數(shù)組的末尾。
前k個(gè)元素： [7, 6, 5]
翻轉(zhuǎn)后： [5, 6, 7]
此時(shí)，數(shù)組的前3個(gè)元素是原數(shù)組的最后3個(gè)元素，而數(shù)組的剩余部分是原數(shù)組的前面部分。最后，翻轉(zhuǎn)剩下的元素（原數(shù)組的前n-k個(gè)元素），將它們移動(dòng)到正確的位置。
剩余的元素： [1, 2, 3, 4]
翻轉(zhuǎn)后： [4, 3, 2, 1]
此時(shí)，數(shù)組的前3個(gè)元素是原數(shù)組的最后3個(gè)元素，數(shù)組的剩余部分是原數(shù)組的前面部分。旋轉(zhuǎn)完成，數(shù)組中的元素已經(jīng)按照要求向右旋轉(zhuǎn)3個(gè)位置。
最終結(jié)果： [5, 6, 7, 1, 2, 3, 4]
通過(guò)三次翻轉(zhuǎn)操作，我們成功地將原數(shù)組向右旋轉(zhuǎn)了3個(gè)位置，而且沒(méi)有使用額外的數(shù)組空間。這個(gè)方法是一個(gè)高效且常用的旋轉(zhuǎn)數(shù)組的方式。
4. 環(huán)形替換
將數(shù)組看作一個(gè)環(huán)，從第一個(gè)元素開(kāi)始，計(jì)算每個(gè)元素在旋轉(zhuǎn)后的位置，然后將元素替換到該位置，直到處理完所有元素，這個(gè)過(guò)程可能需要經(jīng)過(guò)多輪循環(huán)。下面我們來(lái)展示下每輪循環(huán)的具體流程。
假設(shè)我們有一個(gè)數(shù)組 nums，以及需要將它向右旋轉(zhuǎn)k個(gè)位置，其中k等于3。數(shù)組 nums 如下：
nums = [1, 2, 3, 4, 5, 6]
我們將按照下面的步驟開(kāi)始移動(dòng)元素：
- 選擇一個(gè)起始位置，通常從數(shù)組的第一個(gè)元素開(kāi)始，即
nums[0]。 - 獲取到其最終所在位置，根據(jù)旋轉(zhuǎn)的規(guī)則來(lái)獲取。對(duì)于向右旋轉(zhuǎn)，下一個(gè)位置是當(dāng)前位置加上k，即
0 + 3 = 3。 - 保留該位置的數(shù)據(jù)(
nums[3]，即4)，然后將nums[0]的數(shù)放到下標(biāo)等于3的位置下。 - 繼續(xù)移動(dòng)到下一個(gè)位置，根據(jù)旋轉(zhuǎn)規(guī)則，下一個(gè)位置是
3 + 3 = 6，此時(shí)6大于數(shù)組長(zhǎng)度，需要取余數(shù)組長(zhǎng)度，此時(shí)獲取到0, 將之前保留的nums[3]的數(shù)據(jù)賦值到nums[0]當(dāng)中。 - 發(fā)現(xiàn)回到原點(diǎn)位置，此時(shí)完成一輪循環(huán)。
這個(gè)過(guò)程的圖示如下：
初始狀態(tài): [1, 2, 3, 4, 5, 6]
第一步: 1 2 3 4 5 6
↓
第二步: 1 2 3 1 5 6
↓
第三步: 4 2 3 1 5 6
通過(guò)一輪循環(huán)，能夠?qū)⒉糠謹(jǐn)?shù)據(jù)成功放置到正確的位置下。這里我們需要證明下，從原點(diǎn)出發(fā)后，經(jīng)過(guò)一輪循環(huán)，再次回到原點(diǎn)的過(guò)程中，中間會(huì)不會(huì)經(jīng)過(guò)相同的下標(biāo)。因?yàn)槊拷?jīng)過(guò)一個(gè)下標(biāo)，都會(huì)將該元素放到正確的位置，如果重復(fù)到達(dá)，此時(shí)是有問(wèn)題的。
這里我們可以使用數(shù)據(jù)歸納法，來(lái)證明遍歷的過(guò)程是不會(huì)重復(fù)到達(dá)某個(gè)數(shù)組下標(biāo)位置的，除非回到了開(kāi)始的地方。假設(shè)我們?cè)诃h(huán)形數(shù)組中每次向前走k步，但不回到原點(diǎn)。現(xiàn)在我們使用數(shù)學(xué)歸納法來(lái)證明，如果我們?cè)谀骋徊街貜?fù)達(dá)到了某個(gè)位置p，并且之前沒(méi)有回到原點(diǎn)，那么前一個(gè)位置p-1也一定重復(fù)到達(dá)了，以此類(lèi)推，最終說(shuō)明第一個(gè)重復(fù)到達(dá)的點(diǎn)肯定是原點(diǎn)。
但是一次循環(huán)，并不一定能夠經(jīng)過(guò)所有的元素。下面我們需要去獲取到每次循環(huán)能夠到達(dá)的元素的數(shù)量，從而獲取到需要循環(huán)遍歷的次數(shù)。
每次從起點(diǎn)出發(fā)，繞行一圈，再次回到原點(diǎn)的過(guò)程中，其經(jīng)過(guò)的元素的個(gè)數(shù)可以通過(guò)下面公式來(lái)獲取到，公式如下:
(kx + i) % n = i
為什么是這條公式呢? 因?yàn)榛氐皆c(diǎn)，說(shuō)明是經(jīng)過(guò)的長(zhǎng)度必須是數(shù)組長(zhǎng)度 n 的整數(shù)倍，經(jīng)過(guò)的長(zhǎng)度用kx來(lái)表示, k 代表每次移動(dòng)的步數(shù)，而x代表移動(dòng)的次數(shù)。
而 kx 是 n 的整數(shù)倍的數(shù)有無(wú)數(shù)個(gè)，我們只需要第一次到達(dá)原點(diǎn)時(shí)所需要移動(dòng)的步數(shù)，需要獲取到kx 的最小值。因此kx 應(yīng)該是x 和 k 的最小公倍數(shù)，這里最小公倍數(shù)用LCM來(lái)表示。
因此，每次移動(dòng)元素的個(gè)數(shù)為 x = (LCM(k,n)/k)，其中參數(shù)k 和參數(shù)n 都是已知的，基于此能夠獲取到每次移動(dòng)元素的個(gè)數(shù)。下面舉個(gè)例子來(lái)說(shuō)明一下，數(shù)組如下:
nums = [1, 2, 3, 4, 5, 6]
數(shù)組需要向右輪轉(zhuǎn)2個(gè)位置，此時(shí)k = 3， n = 6, 基于此獲取到最小公倍數(shù) = 6?；诠?code>x = (LCM(k,n)/k)，可以獲取到每次循環(huán)移動(dòng)元素的個(gè)數(shù)，這個(gè)例子中，每次循環(huán)移動(dòng)元素的格式為2。
循環(huán)的次數(shù)，為n / x, n 代表數(shù)組的長(zhǎng)度，x 代表每次循環(huán)移動(dòng)元素的數(shù)量。然后每次循環(huán)的開(kāi)頭，都是從上一次循環(huán)的起點(diǎn)的后一個(gè)元素出發(fā)的。 通過(guò)這n / x 次的循環(huán)，就可以將所有數(shù)據(jù)移動(dòng)到正確的位置。
因此，在這道題中，如果我們使用環(huán)形替換，此時(shí)需要先計(jì)算出最小公倍數(shù)LCM(k,n), 然后再基于公式LCM(k,n)/k 獲取到每次移動(dòng)元素的個(gè)數(shù)，然后再通過(guò)n / 每次移動(dòng)元素個(gè)數(shù) 獲取到需要循環(huán)的次數(shù)，公式可以按照下面流程來(lái)進(jìn)行轉(zhuǎn)換:
循環(huán)次數(shù) = n / (lcm(k,n) / k) = nk / lcm(k,n) = gcd(n,k)
其中gcd(n,k) 代表 n 和 k 的最小公約數(shù)。每次循環(huán)中，就從某個(gè)起點(diǎn)出發(fā)，將數(shù)據(jù)移動(dòng)到目標(biāo)位置。
下面我們通過(guò)一個(gè)完整的例子，展示整個(gè)流程，首先數(shù)組如下：
nums = [1, 2, 3, 4, 5, 6]
通過(guò)上面gcd(n,k) 公式計(jì)算，獲取到最大公約數(shù)為3,此時(shí)需要進(jìn)行三輪循環(huán)。
開(kāi)始第一輪移動(dòng)，起點(diǎn)坐標(biāo)為0, 目標(biāo)下標(biāo)為3 , 此時(shí)將nums[0] 的數(shù)據(jù)放到nums[3] 下面；第二步則將原本nums[3] 的元素進(jìn)行移動(dòng)，將其放到 (3+3) % 6 = 0的位置下，接下來(lái)發(fā)現(xiàn)已經(jīng)回到原點(diǎn)，結(jié)束第一輪循環(huán)，如下:
初始狀態(tài): [1, 2, 3, 4, 5, 6]
第一步: 1 2 3 4 5 6
↓
第二步: 1 2 3 1 5 6
↓
第三步: 4 2 3 1 5 6
開(kāi)始第二輪移動(dòng)，本次起點(diǎn)坐標(biāo)為1 , 目標(biāo)下標(biāo)為 4 , 此時(shí)將nums[1] 的數(shù)據(jù)放到nums[4] 下面；第二部將原本nums[4] 的元素進(jìn)行移動(dòng)，將其放到(4+3) % 6 == 1 的位置下。此時(shí)又回到了原點(diǎn)，結(jié)束了第二輪循環(huán)，具體流程如下:
初始狀態(tài): [4, 2, 3, 1, 5, 6]
第一步: 4 2 3 1 5 6
↓
第二步: 1 2 3 1 2 6
↓
第三步: 4 5 3 1 2 6
開(kāi)始第三輪移動(dòng)，本次起點(diǎn)坐標(biāo)為2 , 目標(biāo)下標(biāo)為 5 , 此時(shí)將nums[2] 的數(shù)據(jù)放到nums[5] 下面；第二部將原本nums[5] 的元素進(jìn)行移動(dòng)，將其放到(5+3) % 6 == 2 的位置下。此時(shí)又回到了原點(diǎn)，結(jié)束了第三輪循環(huán)，具體流程如下:
初始狀態(tài): [4, 5, 3, 1, 2, 6]
第一步: 4 5 3 1 2 6
↓
第二步: 1 2 3 1 2 3
↓
第三步: 4 5 6 1 2 3
此時(shí)經(jīng)過(guò)幾輪循環(huán)，成功將數(shù)據(jù)放置到正確的位置，此時(shí)時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)。
5. 總結(jié)
上面描述了輪轉(zhuǎn)數(shù)組這道題的三種解法，包括使用額外數(shù)組，反轉(zhuǎn)數(shù)組，環(huán)形替換這三種方法，同時(shí)也展示了各個(gè)解法過(guò)程中數(shù)據(jù)的流轉(zhuǎn)的順序，希望對(duì)于理解該題能夠起到積極的作用。
代碼已經(jīng)上傳到 github 上，有興趣可以看看。
本文由博客一文多發(fā)平臺(tái) OpenWrite 發(fā)布！
