一:题目描述
- 定义一个函数,实现数组的旋转。如输入
[1, 2, 3, 4, 5, 6, 7]
和key = 3
, 输出[5, 6, 7, 1, 2, 3, 4]
考虑时间复杂度和性能
二:示例与提示
示例 1:
1 | 输入:arr = [1, 2, 3, 4, 5, 6, 7], k = 3 |
示例 2:
1 | 输入:arr = [1, 2, 3, 4, 5, 6, 7], k = -3 |
三:思路
思路一:
- 将数组arr,每次pop最后一个元素,然后unshift添加到第一个元素
思路二:
- 利用slice方法,将数组根据k进行分割成两个数组,然后重新concat连接
四:代码
思路一:
1 | function rotate1(arr: number[], k: number): number[] { |
思路二:
1 | function rotate2(arr: number[], k: number): number[] { |
五:复杂度分析
思路一
- 时间复杂度:O(n ^ 2)
- 对arr数组的遍历为n次,同时
unshift
内置方法,将数组每个元素向后推移,也是为n次
- 对arr数组的遍历为n次,同时
- 空间复杂度:O (1)
思路二
- 时间复杂度:O(1)
- 空间复杂度:O (n)