学生作品网网站,微信商城官方入口,网站开发与网页设计大作业,wordpress head.php题目描述
给定一个整数数组 nums#xff0c;将数组中的元素向右轮转 k 个位置#xff0c;其中 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…题目描述
给定一个整数数组 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
进阶
尽可能想出更多的解决方案至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗
思考一使用额外数组
直接计算每个元素旋转后的新位置借助额外数组存储结果后再复制回原数组。
算法过程
计算有效旋转步数 k k % nn为数组长度创建与原数组等长的新数组遍历原数组将每个元素 nums[i] 放入新数组的 (i k) % n 位置将新数组元素复制回原数组
复杂度时间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;if (k 0) return;const temp [...nums]; // 创建原数组副本for (let i 0; i n; i) {// 计算旋转后位置原索引i的元素移到(i k) % nnums[(i k) % n] temp[i];}
};
思考二环形替换
核心思路从起始位置开始将元素依次移动到旋转后的目标位置形成闭环后切换到下一个未处理的位置直到所有元素都被移动。
算法过程
计算有效旋转步数 k k % n若k为0则返回初始化计数器 count 0记录已处理元素数量从索引0开始循环
记录当前位置 current 和该位置的元素 prev计算目标位置 next (current k) % n交换 prev 与目标位置元素更新 current 为 next重复上述步骤直到回到起始位置形成闭环计数器加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;if (k 0) return;let count 0; // 已处理的元素数量for (let start 0; count n; start) {let current start;let prev nums[start];do {const next (current k) % n;[prev, nums[next]] [nums[next], prev]; // 交换元素current next;count;} while (current ! start); // 回到起点时结束当前环}
};
思考三反转数组
将数组向右旋转k步可通过三次反转操作实现原地修改先反转整个数组再分别反转前k个元素和剩余元素以此等价于直接旋转的效果避免使用额外空间。
算法过程
计算有效旋转步数k k % 数组长度处理k大于数组长度的情况若k为0则无需旋转第一次反转将整个数组从索引0到末尾反转第二次反转将数组前k个元素索引0到k-1反转第三次反转将数组剩余元素索引k到末尾反转
通过三次局部反转最终实现数组整体向右旋转k步的效果时间复杂度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 len nums.length;const count k % len;if (count 0) return;reverse(nums, 0, len-1);reverse(nums, 0, count-1);reverse(nums, count, len-1);
};function reverse(nums, begin, end) {while (begin end) {[nums[begin], nums[end]] [nums[end], nums[begin]];begin;end--;}
}
