2021/07/24 难度:中等
https://leetcode-cn.com/problems/rotate-array/
题目
原题目最好去链接看详情,这里只简单展示题目,不展示详细的例子信息,仅做记录展示。
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
- 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
- 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?
解答
思考流程如下:
- 先将原数组反转,目的是为了将需要移动的子数组放到数组。
- 从位置 k 分割,将分割后的数组再分别反转,拼接在一个临时数组中;
- 将临时数组的数据拷贝到原数组中。
- 要处理移动的位置 k 大于数组长度的情况,因此在算法开始之前,要处理一下 k 的值。k = k % nums.length,比如数组长度为3,k 移动位置为4,那么实际移动的位置就是1(4 % 3 = 1),意思是只要 k 大于数组长度,就是空转,实际移动的位置就是取模。
比如 nums = [1, 2, 3, 4],k = 2,反转后是 [4, 3, 2, 1],需要的结果是 [ 3, 4, 1, 2]。这时,从位置 2 分割,再分别反转,就能得到需要的结果。
TODO:看了题解还有大部分还有两个解法,卷不动休息一下…
代码
function rotate(nums: number[], k: number): void {
k %= nums.length;
nums.reverse()
const before = nums.slice(0, k).reverse()
const after = nums.slice(k).reverse()
const arr = [...before, ...after]
arr.forEach((num, index) => {
nums[index] = num;
})
};
复杂度分析
时间复杂度:O(n),其中 n 是数组的长度。
空间复杂度:O(n)。