Leetcode经典题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 的元素放至新数组下标为 (i+k) 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 开始，最初令 temp=nums[0]。
• 根据规则，位置 0 的元素会放至 (0+k) mod n 的位置，令 x=(0+k) mod n，此时交换 temp 和 nums[x]，完成位置 x 的更新。
• 然后，我们考察位置 x，并交换 temp 和 nums [(x+k) mod n]，从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置 0。每次都考察要更新的位置

容易发现，当回到初始位置 0 时，有些数字可能还没有遍历到，此时我们应该从下一个数字开始重复的过程

怎么才算遍历结束呢？

我们不妨先考虑这样一个问题：从 0 开始不断遍历，最终回到起点 0 的过程中，我们遍历了多少个元素？

由于最终回到了起点，故该过程恰好走了整数数量的圈，不妨设为 a 圈；

再设该过程总共遍历了 b 个元素。

我们用总元素数b 除以 每圈遍历的元素个数n/k 会得到总共遍历的圈数a

因此，我们有 an=bk，即 an 一定为 n,k 的公倍数。又因为我们在第一次回到起点时就结束，因此 a 要尽可能小，故 an 就是 n,k 的最小公倍数 lcm(n,k)，因此 b 就为 lcm(n,k)/k。

这说明单次遍历会访问到 lcm(n,k)/k 个元素。为了访问到所有的元素，我们需要进行遍历的次数为

其中 gcd 指的是最大公约数。

实现代码

使用单独的变量 count 跟踪当前已经访问的元素数量，当 count=n 时，结束遍历过程。

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] 区间的元素即能得到最后的答案。

我们以 n=7，k=3 为例进行如下展示：

实现代码

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

欢迎大家点赞，评论加关注呦