咸阳学校网站建设公司,做网站 图片格式,企鹅号自媒体平台注册,开发公司网站建设文章目录 题目简介题目解答解法一#xff1a;使用额外的数组代码#xff1a;复杂度分析#xff1a; 解法二#xff1a;数组反转代码#xff1a;复杂度分析#xff1a; 题目链接 大家好#xff0c;我是晓星航。今天为大家带来的是 轮转数组 相关的讲解#xff01;#… 文章目录 题目简介题目解答解法一使用额外的数组代码复杂度分析 解法二数组反转代码复杂度分析 题目链接 大家好我是晓星航。今天为大家带来的是 轮转数组 相关的讲解 题目简介
题目解答
解法一使用额外的数组
思路我们可以使用额外的数组来将每个元素放至正确的位置。用 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);}
}这里直接从反转位置开始填入数组元素可以形象理解为我们把起点改变为了ik然后我们在把数组后面填满后再从下标为0的位置开始继续填充元素。(ik)%n的意义即使在nums数组后面填满后然后从第一个位置继续填充。 这里方法的含义是我们从数组newArr的0下标开始复制到nums数组从0下标开始复制n个元素。
复杂度分析
时间复杂度 O(n)其中 n 为数组的长度。
空间复杂度 O(n)。 解法二数组反转
思路我们直接拿官方的图解就可以很轻易地看出思路
代码
class Solution {public void reverse(int[] nums,int start,int end) {while (start end) {int temp nums[start];nums[start] nums[end];nums[end] temp;start start 1;end end - 1;}}public void rotate(int[] nums, int k) {k k % nums.length;reverse(nums,0,nums.length - 1);reverse(nums,0,k-1);reverse(nums,k,nums.length-1);}
}一个很简单的反转数组全部元素的代码 这里k模数组长度的作用就是为了避免要轮转的元素个数比数组本身还大既然轮转一周等于没有轮转因此我们采取这个方法避免数组越界的问题。 这三次轮转的作用也很好解释第一次先把数组整个反转。第二次将前半段反转第三次将后半段反转这样就符合题意了数组是由两个递增数组组合而成。
复杂度分析
时间复杂度O(n)其中 n 为数组的长度。每个元素被翻转两次一共 n 个元素因此总时间复杂度为 O(2n)O(n)。
空间复杂度O(1)。
题目链接
感谢各位读者的阅读本文章有任何错误都可以在评论区发表你们的意见我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞你的每一次鼓励都是作者创作的动力哦
