轮转数组[中等]

优质博文:IT-BLOG-CN

一、题目

给定一个整数数组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)的原地算法解决这个问题。

二、代码

【1】使用额外的数组: 我们可以使用额外的数组来将每个元素放至正确的位置。我们遍历原数组,将原数组下标为i的元素放至新数组下标为(i+k) mod nums.length的位置,最后将新数组拷贝至原数组即可。

class Solution {public void rotate(int[] nums, int k) {// 使用一个等长的数组int[] newArray = new int[nums.length];for (int i = 0; i < nums.length; i++) {newArray[(i + k) % nums.length] = nums[i];}System.arraycopy(newArray, 0, nums, 0, nums.length);}
}

时间复杂度: O(n)其中n为数组的长度。
空间复杂度: O(n)

【2】数组翻转: 该方法基于如下的事实:当我们将数组的元素向右移动k次后,尾部k mod n个元素会移动至数组头部,其余元素向后移动k mod n个位置。

该方法为数组的翻转: 我们可以先将所有元素翻转,这样尾部的k mod n个元素就被移至数组头部,然后我们再翻转[0,k mod n−1]区间的元素和[k mod n,n−1]区间的元素即能得到最后的答案。

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

操作结果
原始数组1 2 3 4 5 6 7
翻转所有元素7 6 5 4 3 2 1
翻转[0,k mod n−1]区间的元素5 6 7 4 3 2 1
翻转 [k mod n,n−1]区间的元素5 6 7 1 2 3 4
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);}private void reverse(int[] nums, int start, int end) {while(start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;++start;--end;}}
}

【3】环状替换: 方法一中使用额外数组的原因在于如果我们直接将每个数字放至它最后的位置,这样被放置位置的元素会被覆盖从而丢失。因此,从另一个角度,我们可以将被替换的元素保存在变量temp中,从而避免了额外数组的开销。

我们从位置0开始,最初令temp=nums[0]。根据规则,位置0的元素会放至(0+k) mod n的位置,令x=(0+k) mod n,此时交换tempnums[x],完成位置x的更新。然后,我们考察位置x,并交换tempnums[(x+k) mod n],从而完成下一个位置的更新。不断进行上述过程,直至回到初始位置0

容易发现,当回到初始位置0时,有些数字可能还没有遍历到,此时我们应该从下一个数字开始重复的过程,可是这个时候怎么才算遍历结束呢?我们不妨先考虑这样一个问题:从0开始不断遍历,最终回到起点0的过程中,我们遍历了多少个元素?由于最终回到了起点,故该过程恰好走了整数数量的圈,不妨设为a圈;再设该过程总共遍历了b个元素。因此,我们有an=bk,即an一定为n,k的公倍数。又因为我们在第一次回到起点时就结束,因此a要尽可能小,故an就是n,k的最小公倍数lcm(n,k),因此b就为lcm(n,k)/k

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

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

我们用下面的例子更具体地说明这个过程:

nums = [1, 2, 3, 4, 5, 6]
k = 2

如果读者对上面的数学推导的理解有一定困难,也可以使用另外一种方式完成代码:使用单独的变量count跟踪当前已经访问的元素数量,当count=n时,结束遍历过程。

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k = 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;int 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)我们只需常数空间存放若干变量。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/249051.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

VueFire:一个一流的 Vue 和 Firebase 体验,包括对 Nuxt 的支持,现在已经稳定了

VueFire&#xff0c;一个一流的 Vue 和 Firebase 体验 — 包括对 Nuxt 的支持&#xff0c;现在已经稳定了。 Vue 和 Firebase 现在比以往任何时候都更好了。 构建更好的VueFire 去年&#xff0c;我们宣布与 Eduardo San Martin Morote 合作&#xff0c;构建一个成熟的 Vue 和…

蓝桥杯嵌入式第七届真题(完成) STM32G431

蓝桥杯嵌入式第七届真题(完成) STM32G431 题目 相关文件 main.c /* USER CODE BEGIN Header */ /********************************************************************************* file : main.c* brief : Main program body**********************…

我的创作纪念日和前端碎碎念

机缘 作为一个前端开发者&#xff0c;我一直热衷于将设计和技术相结合&#xff0c;尽可能提升用户体验。我最初成为创作者的初心源于学习记录&#xff0c;把创作当作一个笔记&#xff0c;希望把自己遇到的问题&#xff0c;以及学习到的实用技巧记录下来&#xff0c;方便学习回…

第九节HarmonyOS 常用基础组件22-Marquee

1、描述 跑马灯组件&#xff0c;用于滚动展示一段单行文本&#xff0c;仅当文本内容宽度超过跑马灯组件宽度时滚动。 2、接口 Marquee(value:{start:boolean, step?:number, loop?:number, fromStart?: boolean ,src:string}) 3、参数 参数名 参数类型 必填 描述 st…

智能指针——浅析

智能指针 本人不才&#xff0c;只能将智能指针介绍一下&#xff0c;无法结合线程进行深入探索 介绍及作用 在异常产生进行跳转时&#xff0c;通过栈帧回收进行内存释放&#xff0c;防止内存泄漏 基于RAII思想可以创建出只能指针 RAII(Resource Acquisition Is Initializatio…

备战蓝桥杯---数据结构与STL应用(入门4)

本专题主要是关于利用优先队列解决贪心选择上的“反悔”问题 话不多说&#xff0c;直接看题&#xff1a; 下面为分析&#xff1a; 很显然&#xff0c;我们在整体上以s[i]为基准&#xff0c;先把士兵按s[i]排好。然后&#xff0c;我们先求s[i]大的开始&#xff0c;即规定选人数…

Neo4j介绍

1.Neo4j概述 Neo4j是一个开源的 无Shcema的 基于java开发的 图形数据库&#xff0c;它将结构化数据存储在图中而不是表中。它是一个嵌入式的、基于磁盘的、具备完全的事务特性的Java持久化引擎。程序数据是在一个面向对象的、灵活的网络结构下&#xff0c;而不是严格、静态的表…

计算机网络-物理层设备(中继器 集线器)

文章目录 中继器中继器的功能再生数字信号和再生模拟信号同一个协议 集线器&#xff08;多口中继器&#xff09;不具备定向传输的原因集线器是共享式设备的原因集线器的所有接口都处于同一个碰撞域&#xff08;冲突域&#xff09;内的原因 小结 中继器 中继器的功能 中继器的…

Qt 5.9.4 转 Qt 6.6.1 遇到的问题总结(三)

1.QSet: toList 中的toList 函数已不存在&#xff0c;遇到xx->toList改成直接用&#xff0c;如下&#xff1a; 2.开源QWT 图形库中QwtDial中的 setPenWidth 变成 setPenWidthF函数。 3.QDateTime 中无setTime_t 改为了setSecsSinceEpoch函数。 4.QRegExp 类已不存在 可以用Q…

给定n个结点的树,u,v两个结点可以配对当且仅当u不是v的祖先且v不是u的祖先,每个结点最多与一个结点配对,求最大配对个数

题目 思路: #include <bits/stdc++.h> using namespace std; #define int long long typedef long long ll; #define pb push_back #define lson p << 1 #define rson p << 1 | 1 #define fi first #define se second const int maxn = 1e6 + 5, maxm = 5e…

免费的ChatGPT网站(7个)

还在为找免费的chatGPT网站或者应用而烦恼吗&#xff1f;博主归纳总结了7个国内非常好用&#xff0c;而且免费的chatGPT网站&#xff0c;AI语言大模型&#xff0c;我们都来接触一下吧。 免费&#xff01;免费&#xff01;免费&#xff01;...&#xff0c;建议收藏保存。 1&…

简单高效 Learn LaTeX 013 - LaTex FloatingBody Tables (44 mins) 浮动体表格

浮动体是LaTex中的一个重要概念&#xff0c;这个视频演示了以浮动体为载体的表格的排版应用。 https://www.douyin.com/user/self?modal_id7305874487138913574&showTabpost

基于 LLM+LlamaIndex+NebulaGraph,构建大模型知识图谱的检索(RAG)方法

最近&#xff0c;围绕着利用 LLM&#xff08;Language Model&#xff09;和知识图谱&#xff08;KG&#xff0c;Knowledge Graphs&#xff09;构建RAG&#xff08;Retrieval Augmented Generation&#xff09;流程引起了很多关注。 在本文中&#xff0c;让我们通过利用 LlamaI…

鸿蒙会取代Android吗?听风就是雨

现在说取代还谈不上&#xff0c;毕竟这需要时间。安卓作为全球第一的手机操作系统&#xff0c;短时间内还无法取代。持平iOS甚至超过iOS有很大可能&#xff0c;最终会呈现“三足鼎立”有望超过安卓基数。 作为全新的鸿蒙操作系统&#xff0c;其现在已经是全栈自研底座。按照鸿…

(Sping Xml方式整合第三方框架)学习Spring的第十天

Spring整合mybatis 1 . 导入Mybatis整合Spring的相关坐标 <dependency><groupId>org.springframework</groupId><artifactId>spring-jdbc</artifactId><version>5.2.13.RELEASE</version></dependency><dependency><…

【20240131】USB相机(查看设备列表、打开设备)

USB相机采集 1、v4l2查看设备列表2、查看具体设备信息3、在桌面打开USB相机 1、v4l2查看设备列表 打开终端&#xff0c;输入&#xff1a;v4l2-ctl --list-devices usb设备在Webcam: Webcam栏&#xff0c;分别是video9和video10&#xff0c;下一步&#xff1a;确定哪一个是接入…

centos7 arm服务器编译安装gcc 9.2

前言 当前电脑的gcc版本为4.8.5,但是在编译其他依赖包的时候,出现各种奇怪的问题,会莫名其妙的中断编译。本地文章讲解如何自编译安装gcc,替换系统自带的gcc。 环境准备 下载缺失依赖库: yum install flex* 否则会报如下错误: gcc 9.2源码:下载地址 开始编译 1、解压…

pve宿主机更改网络导致没网,pve更改ip

一、问题描述 快过年了&#xff0c;我把那台一直在用的小型服务器&#xff0c;带回去了&#xff0c;导致网络发生了变更&#xff0c;需要对网络进行调整&#xff0c;否则连不上网&#xff0c;我这里改的是宿主机&#xff0c;不是pve虚拟机中的系统。 二、解决方法 pve用的是…

Django模型(七)

一、聚合与分组查询 1.1、准备数据 class Cook(models.Model):"""厨师"""name = models.CharField(max_length=32,verbose_name=厨师名)level = models.IntegerField(verbose_name=厨艺等级)age = models.IntegerField(verbose_name=年龄)sect …

【Docker】【深度学习算法】在Docker中使用gunicorn启动多个并行算法服务,优化算法服务:从单进程到并行化

文章目录 优化算法服务&#xff1a;从单进程到并行化单个服务架构多并行服务架构Docker化并指定并行服务数量 扩展知识 优化算法服务&#xff1a;从单进程到并行化 在实际应用中&#xff0c;单个算法服务的并发能力可能无法满足需求。为了提高性能和并发处理能力&#xff0c;我…