189. Rotate Array
給定一個整數數組 nums，將數組向右旋轉 k 步，其中 k 是非負數。
輸入：
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 步：[6,7,1,2,3,4,5]
向右旋轉 3 步：[5,6,7,1,2,3,4]
Python
from typing import List
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
k = k % n # In case k is larger than the length of the array
# Helper function to reverse elements in the array
def reverse(left: int, right: int) -> None:
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# Step 1: Reverse the entire array
reverse(0, n - 1)
# Step 2: Reverse the first k elements
reverse(0, k - 1)
# Step 3: Reverse the rest of the array
reverse(k, n - 1)
28.08MB, 161ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k = k % n; // In case k is larger than the length of the array
// Helper function to reverse elements in the array
auto reverse = [&](int left, int right) {
while (left < right) {
swap(nums[left], nums[right]);
left++;
right--;
}
};
// Step 1: Reverse the entire array
reverse(0, n - 1);
// Step 2: Reverse the first k elements
reverse(0, k - 1);
// Step 3: Reverse the rest of the array
reverse(k, n - 1);
}
};
27.61MB, 16ms
Javascript
/**
* @param {number[]} nums
* @param {number} k
* @return {void} Do not return anything, modify nums in-place instead.
*/
var rotate = function(nums, k) {
const n = nums.length;
k = k % n; // In case k is larger than the length of the array
// Helper function to reverse elements in the array
const reverse = (left, right) => {
while (left < right) {
[nums[left], nums[right]] = [nums[right], nums[left]];
left++;
right--;
}
};
// Step 1: Reverse the entire array
reverse(0, n - 1);
// Step 2: Reverse the first k elements
reverse(0, k - 1);
// Step 3: Reverse the rest of the array
reverse(k, n - 1);
};
61.32MB, 86ms
