189. Rotate Array

🟠   🔖  数组 数学 双指针  🔗 LeetCode

题目

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. 旋转链表
• 🔒 Reverse Words in a String II
• 2607. 使子数组元素和相等

- [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)