算法:将一个数组旋转k步
题目
输入一个数组如 [1,2,3,4,5,6,7],输出旋转 k 步后的数组。
- 旋转 1 步:就是把尾部的 7 放在数组头部前面,也就是
[7,1,2,3,4,5,6] - 旋转 2 步:就是把尾部的 6 放在数组头部前面,也就是
[6,7,1,2,3,4,5] - …
思路
思路1:将数组尾部的元素 pop,然后 unshift 到头部
思路2:将数组拆分成两段,然后通过 concat 拼接在一起
那么哪个是最优解呢?
遵循的原则:复杂度,在前端开发中重时间,轻空间。因为相应速度更重要,占内存的情况不那么重要。
代码
思路1
/*** 旋转数组 k 步 - 使用 pop 和 unshift* @param arr arr* @param k k* @returns arr*/
export function rotate1(arr: number[], k: number): number[] {const length = arr.lengthif (!k || length === 0) return arrconst step = Math.abs(k % length) // abs 取绝对值// O(n^2)for (let i = 0; i < step; i++) {const n = arr.pop()if (n != null) {arr.unshift(n) // 数组是一个有序结构,unshift 操作非常慢!!! O(n)}}return arr
}
思路2
/*** 旋转数组 k 步 - 使用 concat* @param arr arr* @param k k*/export function rotate2(arr: number[], k: number): number[] {const length = arr.lengthif (!k || length === 0) return arrconst step = Math.abs(k % length) // abs 取绝对值// O(1)const part1 = arr.slice(-step) // O(1)const part2 = arr.slice(0, length - step)const part3 = part1.concat(part2)return part3
}
测试
// 功能测试
const arr = [1, 2, 3, 4, 5, 6, 7]
const arr1 = rotate2(arr, 3)
console.info(arr1)// 性能测试
const arr1 = []
for (let i = 0; i < 10 * 10000; i++) {arr1.push(i)
}
console.time('rotate1')
rotate1(arr1, 9 * 10000)
console.timeEnd('rotate1') // 885ms O(n^2)const arr2 = []
for (let i = 0; i < 10 * 10000; i++) {arr2.push(i)
}
console.time('rotate2')
rotate2(arr2, 9 * 10000)
console.timeEnd('rotate2') // 1ms O(1)

可以看到两种方式速度相差了百倍
测试用例
import { rotate1, rotate2 } from './array-rotate'describe('数组旋转', () => {it('正常情况', () => {const arr = [1, 2, 3, 4, 5, 6, 7]const k = 3const res = rotate2(arr, k)expect(res).toEqual([5, 6, 7, 1, 2, 3, 4]) // 断言})it('数组为空', () => {const res = rotate2([], 3)expect(res).toEqual([]) // 断言})it('k 是负值', () => {const arr = [1, 2, 3, 4, 5, 6, 7]const k = -3const res = rotate2(arr, k)expect(res).toEqual([5, 6, 7, 1, 2, 3, 4]) // 断言})it('k 是 0', () => {const arr = [1, 2, 3, 4, 5, 6, 7]const k = 0const res = rotate2(arr, k)expect(res).toEqual(arr) // 断言})it('k 不是数字', () => {const arr = [1, 2, 3, 4, 5, 6, 7]const k = 'abc'// @ts-ignoreconst res = rotate2(arr, k)expect(res).toEqual(arr) // 断言})
})
执行 npx jest xxx.test.ts 即可

复杂度
思路1,时间复杂度为 O(n^2),空间复杂度O(1)
思路2,时间复杂度为 O(1),空间复杂度O(n)
思路1这里为什么是 O(n^2),我们明明只有一次遍历?
答:数组是一个有序结构,unshift 操作非常慢

数组是连续的内存空间,就像这个教室的图,如果要把 F 同学放在前面(unshift操作),那么就得把 ABCDE挨个往后移动一位,所以这个操作是很慢的。但是 push、pop 操作不会,直接给后面添加/删除,前面同学不用动。
相关文章:
算法:将一个数组旋转k步
题目 输入一个数组如 [1,2,3,4,5,6,7],输出旋转 k 步后的数组。 旋转 1 步:就是把尾部的 7 放在数组头部前面,也就是 [7,1,2,3,4,5,6]旋转 2 步:就是把尾部的 6 放在数组头部前面,也就是 [6,7,1,2,3,4,5]… 思路 思…...
使用大华惠智双目半球网络摄像机DH-IPC-HD4140X-E2获取人流量统计数据
记录一下使用Java的SpringBoot大华SDK在智慧公厕项目中使大华惠智双目半球网络摄像机DH-IPC-HD4140X-E2获取人流量统计数据 首先根据说明书登录摄像头,一般摄像头都有自己的账号和密码(可能是admin admin 也可能是admin 888888 还有可能是admin 12345),…...
DC插装式流量阀压力阀
Cartridge Valves 电磁阀 止回阀 运动控制阀 流量控制阀 溢流阀 压力控制阀 顺序阀 梭阀 方向阀 配件 Zero Profile Valves 止回阀 运动控制阀 流量控制阀 溢流阀 梭阀 In-Line Valves 止回阀和梭阀 方向阀 配件 微型系列 AB20S APIDC-30S C10B C10S C10S…...
NumPy 数组学习手册:6~7
原文:Learning NumPy Array 协议:CC BY-NC-SA 4.0 译者:飞龙 六、性能分析,调试和测试 分析,调试和测试是开发过程的组成部分。 您可能熟悉单元测试的概念。 单元测试是程序员编写的用于测试其代码的自动测试。 例如&…...
【笔试强训选择题】Day6.习题(错题)解析
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、Day6习题(错题)解析 二、Day6习题(原题)练习 总结 前言 一、Day6习题(错题)解析…...
磁盘分区-LINUX
1、主分区(primary) 磁盘在Linux当中的命名: IDE /dev/hda hdb SCSI sda sdb 分区数字表示:sda1 、sda2、sda3 磁盘分区相当于给磁盘打隔断 ① 系统中必须要存在的分区,系统盘选择主分区安装 ② 数字编号只能是1-4&am…...
SpringAOP入门基础银行转账实例(进阶版)------------事务处理
SpringAOP入门基础银行转账实例**(进阶版)**------------事务处理 由上一节讲述的通过Connection和QueryRunner对事务进行的处理(详情可以去我之前写的博客文章:https://blog.csdn.net/m0_56245143/article/details/130069160?spm1001.2014…...
【python学习】基础篇-常用函数-format函数 格式化操作
format()可以对数据进行格式化处理操作,语法如下: format(value,format_spec) value 为要转换的数据,fommat spec 为格式化解释, 当参数 format spec 为空时,等同于函数 str(value)的方式。 format spec 可以设置非常复…...
团团面试经验
1、Redis同时访问大量不存在的key会发生什么? 如果是缓存和数据库中都不存在,那么就会发生缓存穿透。 举个例子:某个黑客故意制造一些非法的 key 发起大量请求,导致大量请求落到数据库,结果数据库上也没有查到对应的数…...
今天面了个京东拿 38K 出来的,让我见识到了基础的天花板
今年的春招已经开始了,很多小伙伴收获不错,拿到了心仪的 offer。 各大论坛和社区里也看见不少小伙伴慷慨地分享了常见的软件测试面试题和八股文,为此咱这里也统一做一次大整理和大归类,这也算是划重点了。 俗话说得好࿰…...
Qt创建SDK库(dll动态库)并调用SDK库(dll动态库)
Qt创建SDK库(dll动态库)并调用SDK库(dll动态库) 一、项目场景 在日常的项目中,我们经常会遇到调用别人的数学库、线程库、图形库等操作。这些库通常就被称为SDK,SDK全称是Software Development Kit(软件开发工具包),…...
400以内的蓝牙耳机哪款好?400以内蓝牙耳机排行榜
谈起TWS,无论是传统的音频厂商还是手机厂商,都是其不可或缺的重要产品线,现在很多许多蓝牙耳机都不是千篇一律得形状,市场也鲜有商家在外观上下功夫,下面分享几款400元以内,内外兼具的耳机品牌。 一、南卡…...
基于飞桨实现的特定领域知识图谱融合方案:ERNIE-Gram文本匹配算法
文本匹配任务在自然语言处理领域中是非常重要的基础任务,一般用于研究两段文本之间的关系。文本匹配任务存在很多应用场景,如信息检索、问答系统、智能对话、文本鉴别、智能推荐、文本数据去重、文本相似度计算、自然语言推理、问答系统、信息检索等&…...
前端基础复习
1.什么叫HTML5?和原本的所说的HTML有什么区别? 本质上html和html5是一样的的。区别有: 1. 在文档类型声明上 HTML4.0 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loos…...
Vue2 API-源码解析
目录 Vue.extend(option) delimiters functional Vue.component(id, Function | Object) Vue.directive( id, [definition] ) Vue.filter( id, function) Vue.nextTick() Vue.set() Vue.delete(target, index/key) Vue.compile(template) Vue.observable(object) …...
FastViT: A Fast Hybrid Vision Transformer using Structural Reparameterization
FastViT: A Fast Hybrid Vision Transformer using Structural Reparameterization 论文地址:https://arxiv.org/pdf/2303.14189.pdf 概述 本文提出了一种通用的 CNN 和 Transformer 混合的视觉基础模型 移动设备和 ImageNet 数据集上的精度相同的前提下…...
C/C++文档阅读笔记-A Simple Makefile Tutorial解析
Makefile文件可以使得程序编译变得简单。本博文并不是很系统的讲解makefile,本博文的目标是让读者快速编写自己的makefile文件并能应用到中小项目中。 简单实例 举个例子有下面3个文件,分别是hellomake.c,hellofunc.c,hellomake.…...
GraphSAGE的基础理论
文章目录GraphSAGE原理(理解用)GraphSAGE工作流程GraphSAGE的实用基础理论(编代码用)1. GraphSAGE的底层实现(pytorch)PyG中NeighorSampler实现节点维度的mini-batch GraphSAGE样例PyG中的SAGEConv实现2. …...
Windows 安装 GDAL C++库
Windows 安装 GDAL C库1. 方法1:下载配置网友编译的GDAL版本1.1 下载1.2 配置1.3 测试1.4 缺点2. 方法2:自己编译3. 参考1. 方法1:下载配置网友编译的GDAL版本 1.1 下载 CSDN: GDAL,geos联合编译的库,版本为1.8.0&am…...
二叉树基础概念
1.二叉树种类 1.1 满二叉树 满二叉树:如果一棵二叉树只有度为 0 0 0 的结点和度为 2 2 2 的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。 如图所示: 这棵二叉树为满二叉树,也可以说深度为 k k k&…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...
LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)
在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...
在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7
在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤: 第一步: 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为: // 改为 v…...
