轮转数组[中等]
优质博文: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=7
,k=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
,此时交换temp
和nums[x]
,完成位置x
的更新。然后,我们考察位置x
,并交换temp
和nums[(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)
我们只需常数空间存放若干变量。
相关文章:

轮转数组[中等]
优质博文: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,…...

【SpringBoot系列】自动装配的魅力:Spring Boot vs 传统Spring
IT行业有哪些证书含金量高? 文章目录 IT行业有哪些证书含金量高?强烈推荐前言区别项目配置:依赖管理:内嵌服务器:开发体验: 实例Spring项目示例:Spring Boot项目示例: 总结强烈推荐专栏集锦写在最后 强烈…...

idea自动生成实体类
第一步:idea连接数据库 出现这个就连接成功 第二步:选择数据库 第三步:创建实体类 也可以点击数据库一下子全部创建 选择创建实体类所放位置 这样就完成了,点击看看对其做相应修改...
uniapp -- picker民族选择器
目录 一、实现思路 二、实现步骤 ①view部分展示 ② JavaScript 内容 ③css中样式展示 三、效果展示...
生信学习笔记1:学习如何用OPLS-DA分析代谢组数据(从入门到掌握)
偏最小二乘法(PLS)和正交偏最小二乘法(OPLS)是统计模型,用于寻找两组数据矩阵之间的关系。它们广泛应用于化学计量学、生物信息学、经济预测等领域。 偏最小二乘法(PLS) 偏最小二乘法是一种多变量分析方法,主要用于找到两组数据(通常是预测变量集和响应变量集)之间…...

CDR2024最新版本怎么下载?Coreldraw相关快捷键教程分享
想必从事平面设计的大咖们都知道,Coreldraw是一款优秀的图形设计软件,被广泛地运用在平面设计、包装设计、服装设计各个生活领域,因此了解一些关于CorelDRAW快捷键的知识是很有必要的。因为使用快捷键不仅使用起来方便快捷,而且提…...

C语言实战项目<贪吃蛇>
我们这篇会使用C语言在Windows环境的控制台中模拟实现经典小游戏贪吃蛇 实现基本的功能: 结果如下: 1.一些Win32 API知识 本次实现呢我们会用到一些Win32 API的知识(WIN32 API也就是Microsoft Windows 32位平台的应用程序编程接口): 1)控制窗口大小 我们可以使用…...

人工智能时代:AI提示工程的奥秘 —— 驾驭大语言模型的秘密武器
文章目录 一、引言二、提示工程与大语言模型三、大语言模型的应用实践四、策略与技巧五、结语《AI提示工程实战:从零开始利用提示工程学习应用大语言模型》亮点内容简介作者简介目录获取方式 一、引言 随着人工智能技术的飞速发展,大语言模型作为一种新…...

Idea编写mapper.xml文件提示表名和字段
一、连接database 二、setting- > language -> sql Dialects中 的选项设为 mysql就可以了 三、测试...

解密人工智能:探索机器学习奥秘
🌈个人主页:聆风吟 🔥系列专栏:网络奇遇记、数据结构 🔖少年有梦不应止于心动,更要付诸行动。 文章目录 📋前言一. 机器学习的定义二. 机器学习的发展历程三. 机器学习的原理四. 机器学习的分类…...

C语言第十四弹---函数递归
✨个人主页: 熬夜学编程的小林 💗系列专栏: 【C语言详解】 【数据结构详解】 函数递归 1、递归是什么? 1.1、递归的思想 1.2、递归的限制条件 2、递归举例 2.1、举例1:求n的阶乘 2.1.1、分析和代码实现 2.1.2、…...

etcd自动化安装配置教程
文章目录 前言一、简介1. 简介2. 特点3. 端口介绍 二、etcd安装教程(单机版)1. 复制脚本2. 增加执行权限3. 执行脚本4. 查看启动状态5. 卸载etcd 三、etcd安装教程(集群版)1. 复制脚本2. 增加执行权限3. 分发脚本4. 执行脚本5. 启…...

时间序列预测——GRU模型
时间序列预测——GRU模型 在深度学习领域,循环神经网络(RNN)是处理时间序列数据的一种常见选择。上期已介绍了LSTM的单步和多步预测。本文将深入介绍一种LSTM变体——门控循环单元(GRU)模型,包括其理论基础…...

通用CI/CD软件平台TeamCity全新发布v2023.11——增强Git托管平台的集成
TeamCity是一个通用的 CI/CD 软件平台,可以实现灵活的工作流、协作和开发做法。我们的解决方案将帮助在您的 DevOps 流程中成功实现持续集成、持续交付和持续部署。 TeamCity 2023.11正式版下载 TeamCity 2023.11 带来了矩阵构建和构建缓存等多项备受期待的功能&a…...
C语言:register类型变量
register—— 寄存器存储 register 是 C 语言中的一种存储类别(Storage Class),它用于告诉编译器将变量存储在寄存器中。在 C 语言中,变量的存储位置可以是寄存器、堆栈或静态存储区,使用 register 存储类别可以帮助我…...

android 自定义下拉框
一、 简介: 原生Android 提供的spinner下拉框不怎么方便,样式有点丑。修改起来麻烦,于是就自己动手写了一下拉列表。 实现原理使用的是,popwindow弹框,可实现宽高自定义,下拉列表使用listview. 二、pop弹框…...

揭开时间序列的神秘面纱:特征工程的力量
目录 写在开头1. 什么是特征工程?1.1 特征工程的定义和基本概念1.2 特征工程在传统机器学习中的应用1.3 时间序列领域中特征工程的独特挑战和需求3. 时间序列数据的特征工程技术2.1 数据清洗和预处理2.1.1 缺失值处理2.1.2 异常值检测与处理2.2 时间特征的提取2.2.1 时间戳解析…...

vue3 源码解析(5)— patch 函数源码的实现
什么是 patch 在 vue 中 patch 函数的作用是在渲染的过程中,比较新旧节点的变化,通过打补丁的形式,进行新增、删除、移动或替换操作,此过程避免了大量的 dom 操作,提升了运行的性能。 patch 执行流程 patch 函数整体…...

蓝桥杯2024/1/28----十二届省赛题笔记
题目要求: 2、 竞赛板配置要求 2.1将 IAP15F2K61S2 单片机内部振荡器频率设定为 12MHz。 2.2键盘工作模式跳线 J5 配置为 KBD 键盘模式。 2.3扩展方式跳线 J13 配置为 IO 模式。 2.4 请注意 : 选手需严格按照以上要求配置竞赛板,编写和调…...

STM32+ESP8266 实现物联网设备节点
目录 一、硬件准备 二、编译环境 三、源代码地址 四、说明 五、测试方法 六、所有测试工具和文档 本项目使用stm32F103ZEesp8266实现一个物联网的通信节点,目前支持的协议有mqtt,tcp。后续会持续更新,增加JSON,传感器&#…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...

关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...