【Leetcode資料結構演算法題】輪轉陣列（順序表篇）

題目內容：

給你一個陣列，將陣列中的元素向右輪轉 k 個位置，其中 k 是非負數，

leetcode題目鏈接（點擊即可跳轉）

思路分析

看完題目后，我們首先要做的就是理解題目的含義，也就是審題，從不同維度，不同角度的去設問題并主動回答這些問題，題目中出現了一個我們比較陌生的詞語“輪轉”，可能我們一下子無法理解這個詞是啥子玩意兒，這個時候就可以借助題目中的示例來幫助理解，比如說示例1：

用通俗的話來說就是，向右輪轉1步，就是將最后一個元素放到第一個位置，其余元素位置向右移動一個位置，類似于所有元素向右滑動一個位置，只不過最后一個元素向右滑動的時候需要回到第一個位置，

理解了“輪轉”的含義后，為了更好的理解題目的要求和隱藏含義，我們需要從以下幾個角度進行自我設問：
（1）題目中給的陣列有告訴我們陣列的長度能否為0？
（2）向右輪轉k次的k的實際取值如何，能不能為0？能不能超過陣列本身的長度？
關于（1）（2）這兩個問題，我們可以看題目的提示部分：

根據提示的內容我們可以清楚的知道，陣列的長度至少為1，不能為0，這就解決了問題（1），另外k的取值范圍是0到10^5，雖然沒有直接表明k與陣列長度之間的關系，但是我們可以猜測，k的大小可以超過陣列的長度，也就是說k可以等于0，可以超過陣列本身的長度（可以一直向右轉啊轉），這就解決了問題（2），這兩個問題想清楚后，就可以進行相應的演算法分析和設計了，

方法一：k次輪轉法

這個方法其實可以通過題目給的示例直接想到，
為了簡化問題，我們可以讓k先為1，這樣就是向右輪轉一步，
如果k=2，那么先向右輪轉一步，再向右輪轉一步，
如果k=3…（套娃套娃再套娃）
另外，當k的大小超過陣列的長度時，比如陣列長度為5，k=6，這時候向右進行k次輪轉，相當于前面5次輪轉白做了，只進行了最后1次輪轉，因為輪轉6次和輪轉1次的效果是一樣的，所以實際的輪轉效果應該為 k=k%(陣列的長度），（這里的輪轉效果就是相當于輪轉多少次…我隨便創造的詞方便理解…看不懂也沒關系…）

演算法圖解

函式介面實作

void rotate(int* nums, int numsSize, int k){
    //求出實際輪轉效果
    k = k % numsSize;
    //k為多少，就向右輪轉多少次
    for(int i = 0; i <k; i++){
        //向右輪轉一次的程序
        int temp = nums[numsSize-1];//先保存最后一個元素
        //其余元素向右移動一個位置
        //為了防止資料被覆寫，需要從后往前依次移動
        for(int j = numsSize - 1; j > 0; j--){
            nums[j] = nums[j-1];
        }
        nums[0] = temp;
    }
}

當我們辛辛苦苦寫完代碼，通過測驗用例，進行提交的時候，突然出現了這個

此時心中應該有一萬個問號？？？？飄過，

郁悶的情緒發泄完后，我們還得老老實實的回來分析報錯原因，然后去解決它，（生活不也正是這樣這樣子嗎？盡管我們會遇到各種各樣的挫折、痛苦，但是我們要想生活變得更好，還是需要去勇敢面對它們，去解決它們，逃避，永遠都解決不了問題，只能解決我們自己，）
代碼提交未通過的原因是“超出時間限制”，換句話來說就是“程式運行花的時間太長了”，“時間復雜度未達到要求”，通過分析k次輪轉法演算法的時間復雜度，為O(n^2)，（用了兩層回圈）為了減少時間復雜度，提高演算法的運行速度，一種通常的做法就是“空間換時間”，也就是說通過提高空間復雜度來降低時間復雜度，（學習演算法、資料結構的同學對這種思想應該不陌生）把這種思想應用到本題中，就是通過創建一個臨時陣列，達到降低時間復雜度的效果，
時間復雜度、空間復雜度相關文章：
【資料結構學習筆記】一、資料結構介紹及演算法分析（新手入門進階指南）

方法二：臨時陣列法

創建臨時陣列，可以達到“空間換時間”的目的，這個時候我們還需要回到題目中，看看題目是否對空間復雜度有要求，可以本題對空間復雜度無要求，那就說明這種方法是適用的，
假設k不超過陣列的長度，向右輪轉k次，相當于將后面k個元素移到前面去，將前面的元素向右滑動k個位置，

演算法圖解：

函式介面實作

void rotate(int* nums, int numsSize, int k){
    //求出實際輪轉次數
    k %= numsSize;
    //開辟大小為k的臨時陣列
    int* arr = (int*)malloc(k*sizeof(int));
    //將nums陣列后面k個元素放到臨時陣列中
    int i = numsSize - k;
    int j = 0;
    while(i < numsSize){
        arr[j++] = nums[i++];
    }
    //將nums前面的元素從后往前向后移動k個位置
    for(i = numsSize-k-1; i >=0; i--){
        nums[i+k] = nums[i];
    }
    //將臨時陣列的元素拷貝回nums陣列中
    for(j = 0; j < k; j++){
        nums[j] = arr[j];
    }
}

采用臨時陣列的方式雖然成功的解決了問題，但其空間復雜度為O(n)，假設當我們要處理的資料很多的時候，那么開辟臨時陣列所需要的空間就會很大，有沒有辦法解決這個問題呢？也就是說在保證時間復雜度為O(n)的情況下，降低空間復雜度呢？

方法三：三步翻轉法

這種方式可能我們大多數人都想不出來（我一開始也沒想出來🙂），因為這種方法要通過觀察規律，然后提煉總結出來，（其實就是要接觸過，做過相關題目，比如說反轉字串，翻轉字串，輪轉字串等等），
三步翻轉法的核心思想是：

1）先翻轉陣列后k個元素 （也可以先翻轉前面的元素）
2）再翻轉陣列前面的元素
3）將陣列整體翻轉一下

就能得到最終的結果，是不是很神奇，有沒有感覺跟變魔術一樣？我只想膜拜第一個想出這種方法的大佬Orz，

演算法圖解

函式介面實作

void reverse(int* arr,int begin,int end){
    while(begin < end){
        int temp = arr[begin];
        arr[begin] = arr[end];
        arr[end] = temp;
        begin++;
        end--;
    }
}

void rotate(int* nums, int numsSize, int k){
    k %= numsSize;
    reverse(nums,0,numsSize-k-1);//先翻轉陣列前面的元素
    reverse(nums,numsSize-k,numsSize-1);//再翻轉陣列后面k個元素
    reverse(nums,0,numsSize-1);//最后整體翻轉一下
}

可能這篇文章您閱讀完只花了幾分鐘，甚至幾秒鐘，但卻花了我數個小時甚至一整天的時間┭┮﹏┭┮
原創不易，各位小伙伴點個贊，評論+關注唄~
（小手點贊，水逆退散，逢考必過，諸事順利~）