抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

一:题目描述

  • 定义一个函数,实现数组的旋转。如输入 [1, 2, 3, 4, 5, 6, 7]key = 3, 输出 [5, 6, 7, 1, 2, 3, 4]

    考虑时间复杂度和性能

二:示例与提示

示例 1:

1
2
输入:arr = [1, 2, 3, 4, 5, 6, 7], k = 3
输出:[5, 6, 7, 1, 2, 3, 4]

示例 2:

1
2
输入:arr = [1, 2, 3, 4, 5, 6, 7], k = -3
输出:[5, 6, 7, 1, 2, 3, 4]

三:思路

思路一:

  • 将数组arr,每次pop最后一个元素,然后unshift添加到第一个元素

思路二:

  • 利用slice方法,将数组根据k进行分割成两个数组,然后重新concat连接

四:代码

思路一:

1
2
3
4
5
6
7
8
9
10
11
12
13
function rotate1(arr: number[], k: number): number[] {
//判断空
if (!k || arr.length === 0) return arr
//如果step大于数组本身长度
const step = Math.abs(k % arr.length)
for (let i = 0; i < step; i++) {
const n = arr.pop()
if (n) {
arr.unshift(n)
}
}
return arr
}

思路二:

1
2
3
4
5
6
7
8
9
10
11
function rotate2(arr: number[], k: number): number[] {
//判断空
if (!k || arr.length === 0) return arr
//如果step大于数组本身长度
const step = Math.abs(k % arr.length)
//使用concat
const part1 = arr.slice(-step)
const part2 = arr.slice(0, arr.length - step)
const part3 = part1.concat(part2)
return part3
}

五:复杂度分析

思路一
  • 时间复杂度:O(n ^ 2)
    • 对arr数组的遍历为n次,同时unshift内置方法,将数组每个元素向后推移,也是为n次
  • 空间复杂度:O (1)
思路二
  • 时间复杂度:O(1)
  • 空间复杂度:O (n)

image-20230901175137174

评论