面試經典算法題38-輪轉數組

LeetCode.189
公眾號：阿Q技術站

問題描述

給定一個整數數組 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

思路

1. 處理 k 大于數組長度的情況，因為旋轉一個長度為 n 的數組 n 次，得到的結果和原數組相同。

2. 可以通過三次翻轉實現數組的旋轉。首先，將整個數組翻轉；然后，將前 k 個元素翻轉；最后，將剩余的元素翻轉。

圖解

        +-----------------------------------------+|               開始執行程序               |+-----------------------------------------+|v+-----------------------------------------+|     輸入: nums = [1,2,3,4,5,6,7], k = 3  |+-----------------------------------------+|v+-----------------------------------------+|        處理 k 大于數組長度的情況            ||        k %= 7，得到 k = 3                |+-----------------------------------------+|v+-----------------------------------------+|        定義反轉數組的函數 reverse()        |+-----------------------------------------+|v+-----------------------------------------+|        定義反轉部分數組的函數               || reverse(nums.begin(), nums.begin() + k) |+-----------------------------------------+|v+-----------------------------------------+|          定義反轉剩余部分數組的函數         ||   reverse(nums.begin() + k, nums.end()) |+-----------------------------------------+|v+-----------------------------------------+|             打印當前數組狀態               ||            [1,2,3,4,5,6,7]              |+-----------------------------------------+|v+-----------------------------------------+|        調用 reverse() 反轉整個數組         ||            [7,6,5,4,3,2,1]              |+-----------------------------------------+|v+-----------------------------------------+|              打印當前數組狀態              ||              [7,6,5,4,3,2,1]            |+-----------------------------------------+|v+-----------------------------------------+|        調用 reverse() 反轉前 k 個元素      ||             [5,6,7,4,3,2,1]             |+-----------------------------------------+|v+-----------------------------------------+|              打印當前數組狀態             ||              [5,6,7,4,3,2,1]            |+-----------------------------------------+|v+-----------------------------------------+|        調用 reverse() 反轉剩余元素         ||              [5,6,7,1,2,3,4]            |+-----------------------------------------+|v+-----------------------------------------+|              打印當前數組狀態              ||             [5,6,7,1,2,3,4]             |+-----------------------------------------+|v+-----------------------------------------+|                返回結果                  |+-----------------------------------------+

參考代碼

C++

#include <iostream>
#include <vector>using namespace std;class Solution {
public:void rotate(vector<int>& nums, int k) {int n = nums.size();k %= n; // 處理 k 大于數組長度的情況if (k == 0) return; // 如果 k 等于 0，直接返回// 翻轉整個數組reverse(nums.begin(), nums.end());// 翻轉前 k 個元素reverse(nums.begin(), nums.begin() + k);// 翻轉剩余元素reverse(nums.begin() + k, nums.end());}
};int main() {vector<int> nums = {1, 2, 3, 4, 5, 6, 7}; // 輸入數組int k = 3; // 向右輪轉的位置數Solution solution;solution.rotate(nums, k); // 調用 rotate 方法cout << "旋轉后的數組：";for (int num : nums) {cout << num << " ";}cout << endl;return 0;
}

Java

import java.util.Arrays;class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k %= n; // 處理 k 大于數組長度的情況if (k == 0) return; // 如果 k 等于 0，直接返回// 翻轉整個數組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--;}}public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5, 6, 7}; // 輸入數組int k = 3; // 向右輪轉的位置數Solution solution = new Solution();solution.rotate(nums, k); // 調用 rotate 方法System.out.print("旋轉后的數組：");for (int num : nums) {System.out.print(num + " ");}System.out.println();}
}

Python

class Solution:def rotate(self, nums: List[int], k: int) -> None:n = len(nums)k %= n  # 處理 k 大于數組長度的情況if k == 0:return  # 如果 k 等于 0，直接返回# 翻轉整個數組self.reverse(nums, 0, n - 1)# 翻轉前 k 個元素self.reverse(nums, 0, k - 1)# 翻轉剩余元素self.reverse(nums, k, n - 1)def reverse(self, nums: List[int], start: int, end: int) -> None:while start < end:nums[start], nums[end] = nums[end], nums[start]start += 1end -= 1if __name__ == "__main__":nums = [1, 2, 3, 4, 5, 6, 7]  # 輸入數組k = 3  # 向右輪轉的位置數solution = Solution()solution.rotate(nums, k)  # 調用 rotate 方法print("旋轉后的數組：", nums)