56. 輪轉數組

給定一個整數數組?nums，將數組中的元素向右輪轉?k?個位置，其中?k?是非負數。

示例 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]

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

解題思路

我的思路：每次輪轉其實就是把最后的元素放到前面，那總的結果就是相當于整個數組后k個元素被移動到前面，剩下的元素順次后移。再考慮到假如當k等于數組長度的時候，輪轉k次相當于沒有輪轉。所以這個時候需要優化k的值，例如數組長度n=7，k=10，k%n=10%7=3，即只需要輪轉3次即可就可以避免不必要的重復操作。

如何高效地將數組輪轉k次

方法一：使用額外的數組

創建一個新數組，將原數組的后k個元素放到新數組的前面，然后把原數組前面的元素放到后面。例如，原數組nums，新數組的0到k-1位置是nums的n-k到n-1的元素，k到n-1的位置是nums的0到n-k-1的元素。這種方法的時間復雜度是O(n)，空間復雜度是O(n)。

方法二：三次反轉

假設k=3，數組是1,2,3,4,5,6,7。整個數組反轉之后變成7,6,5,4,3,2,1。然后將前k個元素反轉，再反轉剩下的元素。比如前3個元素反轉后是5,6,7，剩下的反轉是1,2,3,4。這樣整個數組就是5,6,7,1,2,3,4。這三次反轉的結果就是輪轉后的數組。因為反轉操作是原地進行的，時間復雜度是O(n)，空間復雜度是O(1)，更加高效。

代碼實現具體步驟：

1. 計算數組的長度n
2. 處理k的值：首先對k取模數組長度n，k = k % n，避免不必要的重復輪轉。如果k為0，直接返回。
3. 反轉整個數組
4. 反轉前k個元素
5. 反轉剩下的n - k 個元素

反轉數組的部分寫一個輔助函數表示用來反轉數組的一部分，比如從start到end的位置。reverse(nums, start, end)這個函數會將nums數組中從start到end（包括這兩個位置）的元素反轉。

比如，反轉整個數組的話，調用reverse(nums, 0, n-1)。然后反轉前k個元素，調用reverse(nums, 0, k-1)。然后反轉剩下的部分，調用reverse(nums, k, n-1)。

經過三次反轉后，數組就正確了。

程序代碼

class Solution {public void rotate(int[] nums, int k) {// 獲取數組長度int n = nums.length;// 數組為空，直接返回if(n == 0){return;}// 取模處理k大于數組長度的情況，避免無效重復輪轉k = k % n;// k為0，說明無需輪轉，直接返回即可if(k == 0){return;}// 反轉整個數組reverse(nums, 0, n - 1);// 反轉前k個元素reverse(nums, 0, k - 1);// 反轉剩余元素reverse(nums, k, n - 1);}private void reverse(int[] nums, int start, int end){while(start < end){int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}}
}

示例分析：

1. 預處理：

   • 數組長度n = 7，k = 3 % 7 = 3。

2. 三次反轉：

   • 第一次反轉：反轉整個數組[1, 2, 3, 4, 5, 6, 7]?→?[7, 6, 5, 4, 3, 2, 1]。
   • 第二次反轉：反轉前 3 個元素[7, 6, 5]?→?[5, 6, 7]，數組變為[5, 6, 7, 4, 3, 2, 1]。
   • 第三次反轉：反轉剩余 4 個元素[4, 3, 2, 1]?→?[1, 2, 3, 4]，數組變為[5, 6, 7, 1, 2, 3, 4]。

時間復雜度分析：

• 時間復雜度：O (n)。三次反轉操作每次都遍歷數組的一部分，總時間復雜度為線性。
• 空間復雜度：O (1)。只使用了常數級的額外空間，無需創建新數組。