1. 題目描述

題目鏈接: 輪轉數(shù)組

給定一個整數(shù)數(shù)組 nums，將數(shù)組中的元素向右輪轉 k **個位置，其中 k **是非負數(shù)。
示例 1:

輸入: nums = [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:

輸入： nums = [-1,-100,3,99], k = 2
輸出： [3,99,-1,-100]
解釋: 
向右輪轉 1 步: [99,-1,-100,3]
向右輪轉 2 步: [3,99,-1,-100]

2. 使用額外的數(shù)組

一種比較簡單的方法，是創(chuàng)建一個新的數(shù)組，將原數(shù)組的元素按照旋轉后的位置依次放入新數(shù)組中。這種方法需要O(n)的額外空間，其中n是數(shù)組的長度。

下面是一個詳細說明和示意圖，演示如何使用額外的新數(shù)組來實現(xiàn)數(shù)組向右旋轉。假設我們有一個數(shù)組 nums = [1, 2, 3, 4, 5, 6, 7]，要將其向右旋轉3個位置（k=3），我們將創(chuàng)建一個新數(shù)組 new_nums，并按照旋轉后的位置依次將元素從原數(shù)組中放入新數(shù)組中。

創(chuàng)建一個新數(shù)組 new_nums，與原數(shù)組 nums 同樣大小，初始都為0：

原數(shù)組：  [1, 2, 3, 4, 5, 6, 7]
新數(shù)組：  [0, 0, 0, 0, 0, 0, 0]

遍歷原數(shù)組 nums 中的每個元素，將元素按照旋轉后的位置放入新數(shù)組 new_nums 中。為了確定每個元素的新位置，我們可以使用以下公式：新位置 = (當前位置 + k) % 數(shù)組長度。 當前例子中，k=3，數(shù)組長度為7。

開始遍歷，第一個元素1的新位置為 (0 + 3) % 7 = 3，所以將1放入新數(shù)組的第3個位置：

原數(shù)組：  [1, 2, 3, 4, 5, 6, 7]
新數(shù)組：  [0, 0, 0, 1, 0, 0, 0]

第二個元素2的新位置為 (1 + 3) % 7 = 4，所以將2放入新數(shù)組的第4個位置：

原數(shù)組：  [1, 2, 3, 4, 5, 6, 7]
新數(shù)組：  [0, 0, 0, 1, 2, 0, 0]

繼續(xù)這個過程，將所有元素按照新位置放入新數(shù)組：

原數(shù)組：  [1, 2, 3, 4, 5, 6, 7]
新數(shù)組：  [5, 6, 7, 1, 2, 3, 4]

最終旋轉完成，將新數(shù)組 new_nums 的數(shù)據(jù)拷貝到原數(shù)組當中即可:

原數(shù)組：  [5, 6, 7, 1, 2, 3, 4]
新數(shù)組：  [5, 6, 7, 1, 2, 3, 4]

這個過程中，我們創(chuàng)建了一個新數(shù)組，并根據(jù)旋轉后的位置依次將原數(shù)組的元素放入新數(shù)組。這種方法需要O(n)的額外空間，其中n是數(shù)組的長度

3. 數(shù)組翻轉

這道題是將數(shù)組中的元素從一處移動到另一處，通常可以考慮反轉這一操作，因為反轉是可逆的。在向右旋轉問題中，我們可以將旋轉操作看作是將數(shù)組分為兩部分，然后將這兩部分交換位置。反轉這兩個部分的順序就可以實現(xiàn)向右旋轉。

這里通過數(shù)組翻轉來實現(xiàn)向右旋轉時，可以通過三次翻轉操作來完成。這個方法不需要額外的數(shù)組空間，只需要在原數(shù)組上進行操作。下面詳細說明其中的過程，假設有一個數(shù)組 nums = [1, 2, 3, 4, 5, 6, 7]，要將其向右旋轉3個位置(k=3):

首先，將整個數(shù)組翻轉。這將把數(shù)組的最后k個元素移到數(shù)組的前面:

原數(shù)組：  [1, 2, 3, 4, 5, 6, 7]
翻轉后：  [7, 6, 5, 4, 3, 2, 1]

此時，數(shù)組的前3個元素是原數(shù)組的最后3個元素，接下來，翻轉前k個元素。這將把原數(shù)組的最后k個元素移動到數(shù)組的末尾。

前k個元素： [7, 6, 5]
翻轉后：    [5, 6, 7]

此時，數(shù)組的前3個元素是原數(shù)組的最后3個元素，而數(shù)組的剩余部分是原數(shù)組的前面部分。最后，翻轉剩下的元素（原數(shù)組的前n-k個元素），將它們移動到正確的位置。

剩余的元素： [1, 2, 3, 4]
翻轉后：    [4, 3, 2, 1]

此時，數(shù)組的前3個元素是原數(shù)組的最后3個元素，數(shù)組的剩余部分是原數(shù)組的前面部分。旋轉完成，數(shù)組中的元素已經(jīng)按照要求向右旋轉3個位置。

最終結果： [5, 6, 7, 1, 2, 3, 4]

通過三次翻轉操作，我們成功地將原數(shù)組向右旋轉了3個位置，而且沒有使用額外的數(shù)組空間。這個方法是一個高效且常用的旋轉數(shù)組的方式。

4. 環(huán)形替換

將數(shù)組看作一個環(huán)，從第一個元素開始，計算每個元素在旋轉后的位置，然后將元素替換到該位置，直到處理完所有元素，這個過程可能需要經(jīng)過多輪循環(huán)。下面我們來展示下每輪循環(huán)的具體流程。

假設我們有一個數(shù)組 nums，以及需要將它向右旋轉k個位置，其中k等于3。數(shù)組 nums 如下：

nums = [1, 2, 3, 4, 5, 6]

我們將按照下面的步驟開始移動元素：

1. 選擇一個起始位置，通常從數(shù)組的第一個元素開始，即 nums[0]。
2. 獲取到其最終所在位置，根據(jù)旋轉的規(guī)則來獲取。對于向右旋轉，下一個位置是當前位置加上k，即 0 + 3 = 3。
3. 保留該位置的數(shù)據(jù)(nums[3]，即4)，然后將 nums[0] 的數(shù)放到下標等于3 的位置下。
4. 繼續(xù)移動到下一個位置，根據(jù)旋轉規(guī)則，下一個位置是 3 + 3 = 6，此時6 大于數(shù)組長度，需要取余數(shù)組長度，此時獲取到0, 將之前保留的nums[3] 的數(shù)據(jù)賦值到nums[0] 當中。
5. 發(fā)現(xiàn)回到原點位置，此時完成一輪循環(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

通過一輪循環(huán)，能夠將部分數(shù)據(jù)成功放置到正確的位置下。這里我們需要證明下，從原點出發(fā)后，經(jīng)過一輪循環(huán)，再次回到原點的過程中，中間會不會經(jīng)過相同的下標。因為每經(jīng)過一個下標，都會將該元素放到正確的位置，如果重復到達，此時是有問題的。

這里我們可以使用數(shù)據(jù)歸納法，來證明遍歷的過程是不會重復到達某個數(shù)組下標位置的，除非回到了開始的地方。假設我們在環(huán)形數(shù)組中每次向前走k步，但不回到原點。現(xiàn)在我們使用數(shù)學歸納法來證明，如果我們在某一步重復達到了某個位置p，并且之前沒有回到原點，那么前一個位置p-1也一定重復到達了，以此類推，最終說明第一個重復到達的點肯定是原點。

但是一次循環(huán)，并不一定能夠經(jīng)過所有的元素。下面我們需要去獲取到每次循環(huán)能夠到達的元素的數(shù)量，從而獲取到需要循環(huán)遍歷的次數(shù)。

每次從起點出發(fā)，繞行一圈，再次回到原點的過程中，其經(jīng)過的元素的個數(shù)可以通過下面公式來獲取到，公式如下:

(kx + i) % n = i 

為什么是這條公式呢? 因為回到原點，說明是經(jīng)過的長度必須是數(shù)組長度 n 的整數(shù)倍，經(jīng)過的長度用kx來表示, k 代表每次移動的步數(shù)，而x代表移動的次數(shù)。

而 kx 是 n 的整數(shù)倍的數(shù)有無數(shù)個，我們只需要第一次到達原點時所需要移動的步數(shù)，需要獲取到kx 的最小值。因此kx 應該是x 和 k 的最小公倍數(shù)，這里最小公倍數(shù)用LCM來表示。

因此，每次移動元素的個數(shù)為 x = (LCM(k,n)/k)，其中參數(shù)k 和參數(shù)n 都是已知的，基于此能夠獲取到每次移動元素的個數(shù)。下面舉個例子來說明一下，數(shù)組如下:

nums = [1, 2, 3, 4, 5, 6]

數(shù)組需要向右輪轉2個位置，此時k = 3， n = 6, 基于此獲取到最小公倍數(shù) = 6。基于公式x = (LCM(k,n)/k)，可以獲取到每次循環(huán)移動元素的個數(shù)，這個例子中，每次循環(huán)移動元素的格式為2。

循環(huán)的次數(shù)，為n / x, n 代表數(shù)組的長度，x 代表每次循環(huán)移動元素的數(shù)量。然后每次循環(huán)的開頭，都是從上一次循環(huán)的起點的后一個元素出發(fā)的。 通過這n / x 次的循環(huán)，就可以將所有數(shù)據(jù)移動到正確的位置。

因此，在這道題中，如果我們使用環(huán)形替換，此時需要先計算出最小公倍數(shù)LCM(k,n), 然后再基于公式LCM(k,n)/k 獲取到每次移動元素的個數(shù)，然后再通過n / 每次移動元素個數(shù) 獲取到需要循環(huán)的次數(shù)，公式可以按照下面流程來進行轉換:

循環(huán)次數(shù) = n / (lcm(k,n) / k) = nk / lcm(k,n) =  gcd(n,k)

其中gcd(n,k) 代表 n 和 k 的最小公約數(shù)。每次循環(huán)中，就從某個起點出發(fā)，將數(shù)據(jù)移動到目標位置。

下面我們通過一個完整的例子，展示整個流程，首先數(shù)組如下：

nums = [1, 2, 3, 4, 5, 6]

通過上面gcd(n,k) 公式計算，獲取到最大公約數(shù)為3,此時需要進行三輪循環(huán)。

開始第一輪移動，起點坐標為0, 目標下標為3 , 此時將nums[0] 的數(shù)據(jù)放到nums[3] 下面；第二步則將原本nums[3] 的元素進行移動，將其放到 (3+3) % 6 = 0 的位置下，接下來發(fā)現(xiàn)已經(jīng)回到原點，結束第一輪循環(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

開始第二輪移動，本次起點坐標為1 , 目標下標為 4 , 此時將nums[1] 的數(shù)據(jù)放到nums[4] 下面；第二部將原本nums[4] 的元素進行移動，將其放到(4+3) % 6 == 1 的位置下。此時又回到了原點，結束了第二輪循環(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

開始第三輪移動，本次起點坐標為2 , 目標下標為 5 , 此時將nums[2] 的數(shù)據(jù)放到nums[5] 下面；第二部將原本nums[5] 的元素進行移動，將其放到(5+3) % 6 == 2 的位置下。此時又回到了原點，結束了第三輪循環(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

此時經(jīng)過幾輪循環(huán)，成功將數(shù)據(jù)放置到正確的位置，此時時間復雜度為O(n),空間復雜度為O(1)。

5. 總結

上面描述了輪轉數(shù)組這道題的三種解法，同時也展示了各個解法過程中數(shù)據(jù)的流轉，希望對于理解該題能夠起到積極的作用。
代碼已經(jīng)上傳到github上，有興趣可以看看。