【前端算法】将一个数组旋转K步

简介: 使用typescript完成将一个数组旋转K步的过程
  • 输入一个数组[1, 2, 3, 4, 5, 6, 7]
  • k = 3, 即旋转3步
  • 输出[5, 6, 7, 1, 2, 3, 4]

思路

  • 1、把末尾的元素挨个 pop ,然后 unshift 到数组前面
  • 2、把数组拆分,最后concat 拼接到一起

代码示例1

function rotate1 (arr: number[], k?:number): number[] {
  const len = arr.length
  if (!k || len === 0) return arr;

  const step = Math.abs(k % len); // 取绝对值,防止step大于数组长度的情况

  for (let i = 0; i < step; i++) {
    const n = arr.pop()

    if (typeof n !== "undefined") {
      arr.unshift(n)
    }
  }

  return arr;
}

代码示例2

function rotate2 (arr: number[], k?: number): number[] {
  const len = arr.length
  if (!k || len === 0) return arr;

  const step = Math.abs( k % len); // 取绝对值,防止step大于数组长度的情况

  const part1 = arr.slice(-step);
  const part2 = arr.slice(0,len - step);
  const part3 = part1.concat(part2)

  return part3
}

关于 k % len 当k是字符串时,取余的结果是NaN。在示例1中 i < NaN === false, 在示例2中arr.slice(-NaN) === arr

功能测试

const res = rotate1([1, 2, 3, 4, 5, 6, 7],-3)
const res2 = rotate2 ([1, 2, 3, 4, 5, 6, 7],-3)
console.log(res) // [5, 6, 7, 1, 2, 3, 4]
console.log(res2) // [5, 6, 7, 1, 2, 3, 4]

JEST单元测试

describe('数组旋转', () => {
    it('正常情况', () => {
        const arr = [1, 2, 3, 4, 5, 6, 7]
        const k = 3
        const res = rotate1(arr,k)
        expect(res).toEqual([5, 6, 7, 1, 2, 3, 4]) // 断言
    })
    
    it('数组为空', () => {
        const res = rotate1([],3)
        expect(res).toEqual([]) // 断言
    })
    
    it('k 是负值', () => {
        const arr = [1, 2, 3, 4, 5, 6, 7]
        const k = -3
        const res = rotate1(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 = 0
        const res = rotate1(arr,k)
        expect(res).toEqual(arr) // 断言
    })
    
    it('k 不是数值', () => {
        const arr = [1, 2, 3, 4, 5, 6, 7]
        const k = 'abc'
        
        @ts-ignore
        const res = rotate1(arr,k)
        expect(res).toEqual(arr) // 断言
    })
})

性能测试

const testArr1 = []
for(let i = 0; i < 10 * 10000; i++){
  testArr1.push(i)
}

console.time('rotate1')
rotate1(testArr1,9 * 10000)
console.timeEnd('rotate1')

const testArr2 = []
for(let i = 0; i < 10 * 10000; i++){
  testArr2.push(i)
}
console.time('rotate2')
rotate2(testArr2,9 * 10000)
console.timeEnd('rotate2')

结果:

rotate1: 3.611s
rotate2: 1.147ms

思路2 性能 远超思路1

复杂度分析

  • 思路1: 时间复杂度O(n ^2), 空间复杂度O(1)
  • 思路2:时间复杂度O(1),空间复杂度O(n)

数组是一个连续的内存空间,unshift操作是一个有序的操作,相当于对数组进行了一次遍历,所以非常慢!!!

所以思路1的时间复杂度不是O(n)而是O(n ^ 2)!

正确选择答案

  • 选择思路2:拆分数组,最后concat拼接,返回
  • 时间复杂度O(1),足够快
  • 空间复杂度O(n),对于前端(重时间,轻空间)可以接受
相关文章
|
2月前
|
算法 数据安全/隐私保护 开发者
马特赛特旋转算法:Python的随机模块背后的力量
马特赛特旋转算法是Python `random`模块的核心,由松本真和西村拓士于1997年提出。它基于线性反馈移位寄存器,具有超长周期和高维均匀性,适用于模拟、密码学等领域。Python中通过设置种子值初始化状态数组,经状态更新和输出提取生成随机数,代码简单高效。
118 63
|
3月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
49 0
|
17天前
|
机器学习/深度学习 前端开发 算法
婚恋交友系统平台 相亲交友平台系统 婚恋交友系统APP 婚恋系统源码 婚恋交友平台开发流程 婚恋交友系统架构设计 婚恋交友系统前端/后端开发 婚恋交友系统匹配推荐算法优化
婚恋交友系统平台通过线上互动帮助单身男女找到合适伴侣,提供用户注册、个人资料填写、匹配推荐、实时聊天、社区互动等功能。开发流程包括需求分析、技术选型、系统架构设计、功能实现、测试优化和上线运维。匹配推荐算法优化是核心,通过用户行为数据分析和机器学习提高匹配准确性。
54 3
|
3月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
54 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
3月前
|
JavaScript 前端开发 算法
前端优化之超大数组更新:深入分析Vue/React/Svelte的更新渲染策略
本文对比了 Vue、React 和 Svelte 在数组渲染方面的实现方式和优缺点,探讨了它们与直接操作 DOM 的差异及 Web Components 的实现方式。Vue 通过响应式系统自动管理数据变化,React 利用虚拟 DOM 和 `diffing` 算法优化更新,Svelte 通过编译时优化提升性能。文章还介绍了数组更新的优化策略,如使用 `key`、分片渲染、虚拟滚动等,帮助开发者在处理大型数组时提升性能。总结指出,选择合适的框架应根据项目复杂度和性能需求来决定。
|
3月前
|
人工智能 前端开发 JavaScript
拿下奇怪的前端报错(一):报错信息是一个看不懂的数字数组Buffer(475) [Uint8Array],让AI大模型帮忙解析
本文介绍了前端开发中遇到的奇怪报错问题,特别是当错误信息不明确时的处理方法。作者分享了自己通过还原代码、试错等方式解决问题的经验,并以一个Vue3+TypeScript项目的构建失败为例,详细解析了如何从错误信息中定位问题,最终通过解读错误信息中的ASCII码找到了具体的错误文件。文章强调了基础知识的重要性,并鼓励读者遇到类似问题时不要慌张,耐心分析。
|
3月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
31 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
3月前
|
JSON 前端开发 数据格式
@RequestMapping运用举例(有源码) 前后端如何传递参数?后端如何接收前端传过来的参数,传递单个参数,多个参数,对象,数组/集合(有源码)
文章详细讲解了在SpringMVC中如何使用`@RequestMapping`进行路由映射,并介绍了前后端参数传递的多种方式,包括传递单个参数、多个参数、对象、数组、集合以及JSON数据,并且涵盖了参数重命名和从URL中获取参数的方法。
273 0
@RequestMapping运用举例(有源码) 前后端如何传递参数?后端如何接收前端传过来的参数,传递单个参数,多个参数,对象,数组/集合(有源码)
|
3月前
|
移动开发 算法 前端开发
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
前端常用算法全解:特征梳理、复杂度比较、分类解读与示例展示
38 0
|
4月前
|
算法 前端开发 机器人
一文了解分而治之和动态规则算法在前端中的应用
该文章详细介绍了分而治之策略和动态规划算法在前端开发中的应用,并通过具体的例子和LeetCode题目解析来说明这两种算法的特点及使用场景。
一文了解分而治之和动态规则算法在前端中的应用