《力扣算法训练提升》图解数组篇-打卡数组统计-【189】旋转数组
《力扣算法训练提升》图解数组篇-打卡数组统计-【189】旋转数组
今日份打卡题[189. 旋转数组]
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
具体描述
解题讨论
讨论归纳一：辅助数组，划分旋转区域
第一步：根据数组长度 N 和跨步 K 计算出需要转移至数组头部的元素个数
第二步：将数组划分为两个区域
注意：（逻辑区域，思想区域，这里是为了方便理解，不需要真实状态标注）
区域一：需要旋转到右边的数（头部需要旋转到尾部的元素）
区域二：需要旋转到左边的数（尾部需要旋转到头部的元素）
第三步：迁移数据到辅助数组
先迁移区域二，在迁移区域一
第四步：拷贝回原数组
区域划分图
动画模拟
示例一：辅助数组，划分旋转区域
public void rotate(int[] nums, int k) {
// 计算尾部需要移至头部元素个数
k %= nums.length;
int N = nums.length;
int j = 0;
int[] help = new int[nums.length];
// 归位区域二
// 即归位需要移至头部的元素
for (int i = N - k; i < N; i++) {
help[j++] = nums[i];
}
// 归位区域一
// 即归位需要移至尾部的元素
for (int i = 0; i < N - k; i++) {
help[j++] = nums[i];
}
System.arraycopy(help, 0, nums, 0, N);
}
复杂度分析
时间复杂度：O(n)。遍历数组需要 O(n) 的时间。
空间复杂度：O(n)。需要辅助数组。
讨论归纳二：辅助数组，前世今生
重点：数组元素 a[i] 通过潘多拉魔盒找到今生（a[i] 旋转后在新的位置下标 j）
遍历数组，找到前世 a[i] 的今生 j, 并安排到辅助数组对应的位置
魔盒：j = (i+k) % N
前世今生图
动画模拟
示例二：辅助数组，前世今生
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] help = new int[n];
for (int i = 0; i < n; ++i) {
// 旋转 k, 相当于 nums[i] 元素向后跨步 k 个下标
// nums 数组下标范围是 [0, N-1]
// 跨步后下标超过N-1，从 0 继续跨步
// 计算 nums[i] 旋转后在辅助数组中的相对位置
int m = (i + k) % n;
help[m] = nums[i];
}
System.arraycopy(help, 0, nums, 0, n);
}
复杂度分析
时间复杂度：O(n)。其中 n 为数组的长度。
空间复杂度：O(n)。需要额外空间。
讨论归纳三：翻转数组
归纳一中，囧囧划分了旋转区域，利用辅助数组实现区域旋转，实现了数组旋转的目的。
实际上，我们不需要借助辅助数组也能实现区域旋转，达到交换目的。
首先还是利用模运算计算出需要转移到数组头部的元素个数。
在通过翻转数组实现旋转。
1 2 3 4 5 6 7 K=3
第一步：根据数组长度 N 和跨步 K 计算出需要转移至数组头部的元素个数
第二步：将数组划分为两个区域
注意：（逻辑区域，思想区域，这里是为了方便理解，不需要真实状态标注）
区域一：需要旋转到右边的数（头部需要旋转到尾部的元素）
1 2 3 4
区域二：需要旋转到左边的数（尾部需要旋转到头部的元素）
5 6 7
第三步：翻转整个数组
7 6 5 4 3 2 1
第四部：翻转区域二，在翻转区域一
翻转区域二 5 6 7
翻转区域一 1 2 3 4
5 6 7 1 2 3 4
动画模拟
示例三：翻转数组
public void rotate(int[] nums, int k) {
// 计算尾部需要移至头部元素个数
k %= nums.length;
// 翻转数组所有元素
reverse(nums, 0, nums.length - 1);
// 翻转已经移至头部的元素
reverse(nums, 0, k - 1);
// 翻转已经移至尾部的元素
reverse(nums, k, nums.length - 1);
}
// 翻转 [start, end] 范围内的数
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start += 1;
end -= 1;
}
}
短话长说
学算法先学什么？什么阶段该刷什么题？
关注我，日常打卡算法图解。
按照力扣题目类别结构化排序刷题，从低阶到高阶，图解算法(更新中…)，有兴趣的童鞋，欢迎一起从小白开始零基础刷力扣，共同进步！
回复：678，获取已分类好的部分刷题顺序，后续内容会持续更新，感兴趣的小伙伴自由拿取！
另外，有关分类，求小伙伴们不要再问我最后一类的起名了，奇技淫巧是个褒义词，意思是指新奇的技艺和作品。
力扣修炼体系题目，题目分类及推荐刷题顺序及题解
目前暂定划分为四个阶段：
算法低阶入门篇--武者锻体
算法中级进阶篇--武皇炼心
算法高阶强化篇--武帝粹魂
算法奇技淫巧篇--战斗秘典
以上分类原谅我有个修仙梦...
缺漏内容，正在努力整理中…
