189. Rotate Array
189. Rotate Array
题目
Given an integer array nums
, rotate the array to the right by k
steps, where k
is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5
Follow up:
- Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
- Could you do it in-place with
O(1)
extra space?
题目大意
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
解题思路
- 解法一,使用一个额外的数组,先将原数组拷贝一份,再将下标为
(i + n - k) mod n
的元素移动到 i 的位置即可。 - 解法二,由于题目要求不能使用额外的空间,所以本题最佳解法不是解法一。翻转最终态是,末尾
k mod n
个元素移动至了数组头部,剩下的元素右移k mod n
个位置至最尾部。确定了最终态以后再变换就很容易。先将数组中所有元素从头到尾翻转一次,尾部的所有元素都到了头部,然后再将[0,(k mod n) − 1]
区间内的元素翻转一次,最后再将[k mod n, n − 1]
区间内的元素翻转一次,即可满足题目要求。
代码
解法一
// 解法一 时间复杂度 O(n),空间复杂度 O(n)
/**
* @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;
let arr = [...nums];
for (let i = 0; i < n; i++) {
nums[i] = arr[(i + n - k) % n];
}
};
解法二
// 解法二 时间复杂度 O(n),空间复杂度 O(1)
/**
* @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;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
};
var reverse = function (arr, start, end) {
let mid = (end - start) / 2;
let temp;
for (let i = 0; i < mid; i++) {
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
return arr;
};
相关题目
相关题目
- [61. 旋转链表](./0061.md)
- [🔒 Reverse Words in a String II](https://leetcode.com/problems/reverse-words-in-a-string-ii)
- [2607. 使子数组元素和相等](https://leetcode.com/problems/make-k-subarray-sums-equal)