威海制作网站,网页设计教程下载,韩国小游戏网站,手机网络优化题目描述 给定一个整数数组 nums#xff0c;将数组中的元素向右轮转 k 个位置#xff0c;其中 k 是非负数。 输入输出示例 #xff1a; 输入: 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] 向右… 题目描述 给定一个整数数组 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] 解题方案 模除操作 方式一使用额外的数组
算法思想
使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度我们遍历原数组将原数组下标为 i 的元素放至新数组下标为 (ik) mod n 的位置最后将新数组拷贝至原数组即可
实现代码
class Solution {public void rotate(int[] nums, int k) {//获取数组长度int n nums.length;//创建一个新数组int[] newArr new int[n];//遍历原数组将数组放到正确的位置for (int i 0; i n; i) {newArr[(i k) % n] nums[i];}System.arraycopy(newArr, 0, nums, 0, n);}
}
复杂度分析
时间复杂度 O(n)其中 n 为数组的长度。空间复杂度 O(n)。
方法二环状替换
算法思想
为了防止元素覆盖的问题因此从另一个角度我们可以将被替换的元素保存在变量 temp 中从而避免了额外数组的开销。
我们用下面的例子更具体地说明这个过程 nums [1, 2, 3, 4, 5, 6] k 2 我们从位置 0 开始最初令 tempnums[0]。根据规则位置 0 的元素会放至 (0k) mod n 的位置令 x(0k) mod n此时交换 temp 和 nums[x]完成位置 x 的更新。然后我们考察位置 x并交换 temp 和 nums [(xk) mod n]从而完成下一个位置的更新。不断进行上述过程直至回到初始位置 0。每次都考察要更新的位置
容易发现当回到初始位置 0 时有些数字可能还没有遍历到此时我们应该从下一个数字开始重复的过程 怎么才算遍历结束呢 我们不妨先考虑这样一个问题从 0 开始不断遍历最终回到起点 0 的过程中我们遍历了多少个元素 由于最终回到了起点故该过程恰好走了整数数量的圈不妨设为 a 圈 再设该过程总共遍历了 b 个元素。 我们用总元素数b 除以 每圈遍历的元素个数n/k 会得到总共遍历的圈数a 因此我们有 anbk即 an 一定为 n,k 的公倍数。又因为我们在第一次回到起点时就结束因此 a 要尽可能小故 an 就是 n,k 的最小公倍数 lcm(n,k)因此 b 就为 lcm(n,k)/k。 这说明单次遍历会访问到 lcm(n,k)/k 个元素。为了访问到所有的元素我们需要进行遍历的次数为 其中 gcd 指的是最大公约数。 实现代码
使用单独的变量 count 跟踪当前已经访问的元素数量当 countn 时结束遍历过程。
class Solution {public void rotate(int[] nums, int k) {//数组长度int n nums.length;k k % n;//遍历次数 k和n的最大公约数int count gcd(k, n);//循环遍历for (int start 0; start count; start) {//当前遍历的数组下标int current start;//开始时的数组元素int prev nums[start];do {//将要更新的数组下标int next (current k) % n;//将被覆盖的数组值赋给tempint temp nums[next];//更新nums[next] prev;prev temp;current next;} while (start ! current);}}public int gcd(int x, int y) {return y 0 ? gcd(y, x % y) : x;}
}
复杂度分析
时间复杂度O(n)其中 n 为数组的长度。每个元素只会被遍历一次。
空间复杂度O(1)。我们只需常数空间存放若干变量。
方法三数组翻转
算法思想
该方法基于如下的事实当我们将数组的元素向右移动 k 次后尾部 k mod n 个元素会移动至数组头部其余元素向后移动 k mod n 个位置。
实现步骤
我们可以先将所有元素翻转这样尾部的 k mod n 个元素就被移至数组头部然后我们再翻转 [0,kmodn−1] 区间的元素和 [kmodn,n−1] 区间的元素即能得到最后的答案。
我们以 n7k3 为例进行如下展示 实现代码
class Solution {public void rotate(int[] nums, int k) {//确定分开反转的位置k % nums.length;//反转整个数组reverse(nums, 0, nums.length - 1);//反转前一半reverse(nums, 0, k - 1);//反转后一半reverse(nums, k, nums.length - 1);}//数组翻转public void reverse(int[] nums, int start, int end) {while (start end) {int temp nums[start];nums[start] nums[end];nums[end] temp;start 1;end - 1;}}
}复杂度分析
时间复杂度O(n)其中 n 为数组的长度。每个元素被翻转两次一共 n 个元素因此总时间复杂度为 O(2n)O(n)。
空间复杂度O(1)。 欢迎大家点赞评论加关注呦
