定义一个函数,实现数组的旋转。如输入 [1, 2, 3, 4, 5, 6, 7] key = 3 , 输出 [5, 6, 7, 1, 2, 3, 4]
考虑时间复杂度和性能

  • k 后面的元素,挨个 pop 然后 unshift 到数组前面
  • k 后面的所有元素拿出来作为 part1
  • k 前面的所有元素拿出来作为 part2
  • 返回 part1.concat(part2)
  • * 旋转数组 k 步 - 使用 concat * @param arr arr * @param k k export function rotate2 (arr: number[], k: number) : number[] { const length = arr.length if (!k || length === 0 ) return arr const 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

    经过性能测试,知道“思路2”性能更优。看来,思路简单并不一定性能最优。

    【注意】我看到网上有很多人为“思路1”的写法点赞,要保持独立思考,不要从众!

    时间复杂度

    复杂度用 O 表示,说的是 数量级 ,而不是具体的数字,如

  • O(2) O(3) O(100) 其实都是 O(1)
  • O(n) O(2 * n) 其实都是 O(n)
  • 常见的时间复杂度

  • O(1) 无循环
  • O(n) 单次循环
  • O(logn) 二分法
  • O(n*logn) 单次循环 & 二分法
  • O(n^2) 嵌套循环
  • 【注意】如果你用到了 API (如数组 unshift )要结合数据结构去分析复杂度。 要看到代码的本质

    空间复杂度

    算法需要额外定义多少变量?

  • O(1) 定义了为数不多的变量,和 n 无关
  • O(n) 需要定义和 n 级别的变量,如额外复制一个同样的数组
  • 其他不常见
  • 前端算法通常不太考虑空间复杂度,或者它比时间复杂度要次要的多。
    因为前端环境,通常内存都是足够的,或者内存不够通常也是其他因素(如媒体文件)。

    时间复杂度

  • 思路1 - 看代码时间复杂度是 O(n) 但数组是有序结构 unshift 本身就是 O(n) 复杂度 ,所以实际复杂度是 O(n^2)
  • 思路2 - O(1) slice concat 不会修改原数组,而数组是有序结构,复杂度是 O(1)
  • 空间复杂度

  • 思路1 - O(1)
  • 思路2 - O(n)
  • 整体分析,选择“思路2”

    考虑参数非法情况,代码鲁棒性

    算法复杂度

  • 要看到全部的时间复杂度(包括 API)
  • 重时间,轻空间
  • 数组是有序结构, shift unshift 等要慎用

    扩展 - 不要过度优化

    其实还有一种思路,时间复杂度 O(n) ,空间复杂度 O(1) ,思路:

  • k 前面的元素移动到 i + (length - k) 的位置
  • k 后面的元素移动到 i - k 的位置
  • 但不推荐这样的做法

  • 前端重时间、轻空间,优先考虑时间复杂度,而非空间复杂度
  • 代码是否易读,是否易沟通 —— 这个比性能更重要!人力成本永远是最贵的!!
  • 分类:
    前端
  •