189. 轮转数组

🟠   🔖  数组 数学 双指针  🔗 力扣 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 的位置即可。

复杂度分析

• 时间复杂度：O(n)，其中 n 为给定数组的长度。
• 空间复杂度：O(n)，使用了长度为 n 的额外空间。

---

思路二

由于题目要求不能使用额外的空间，所以本题最佳解法不是解法一。翻转最终态是，末尾 k mod n 个元素移动至了数组头部，剩下的元素右移 k mod n 个位置至最尾部。确定了最终态以后再变换就很容易。先将数组中所有元素从头到尾翻转一次，尾部的所有元素都到了头部，然后再将 [0,(k mod n) − 1] 区间内的元素翻转一次，最后再将 [k mod n, n − 1] 区间内的元素翻转一次，即可满足题目要求。

复杂度分析

• 时间复杂度：O(n)，其中 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;
	let arr = [...nums];
	for (let i = 0; i < n; i++) {
		nums[i] = arr[(i + n - k) % 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;
	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	旋转链表	[✓]	链表 双指针
186	反转字符串中的单词 II 🔒		双指针 字符串
2607	使子数组元素和相等		数组 数学 数论 1+