数组
大家好，我是老马。
今天我们一起来学习一下数组这种数据结构。
主要知识
数组需要拆分下面几个部分：
-
理论介绍
-
源码分析
-
数据结构实现？
-
题目练习（按照算法思想分类）
-
梳理对应的 sdk 包
-
应用实战
因为这个是 leetcode 系列，所以重点是 4、5(对4再一次总结)。
为了照顾没有基础的小伙伴，会简单介绍一下1的基础理论。
简单介绍1，重点为4。其他不是本系列的重点。
T1089 复写零
给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
示例 1：
输入：arr = [1,0,2,3,0,4,5,0] 输出：[1,0,0,2,3,0,0,4] 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
示例 2：
输入：arr = [1,2,3] 输出：[1,2,3] 解释：调用函数后，输入的数组将被修改为：[1,2,3]
提示：
1 <= arr.length <= 104 0 <= arr[i] <= 9
v1-暴力方式
思路
就是最朴素的符合题目意思的解法，没有任何技巧。
解法
public void duplicateZeros(int[] arr) {
int n = arr.length;
for(int i = 0; i < n; i++) {
if(arr[i] == 0) {
// 当前位置后面的全部往后移动一个位置
for(int j = n-1; j >= i+1; j--) {
arr[j] = arr[j-1];
}
// 下一个位置插入0
i++;
if(i >= n) {
return;
}
arr[i] = 0;
}
// 提前结束
if(i >= n) {
return;
}
}
}
效果
17ms 击败 6.70%
竟然 AC 了，大概这就是 easy 的理由。
v2-空间换时间
思路
虽然这一题要求原地排序，不过我们用这个方法用来作为双指针的过渡。
left 对应 temp 数字下标。
right 对应原始的下标。
我们可以用 left right 两个指针，遇到 0 就往 left 多加一个0。
如果 left 长度和以前一样，结束。
实现
public void duplicateZeros(int[] arr) {
int n = arr.length;
int left = 0;
int right = 0;
// 临时数组
int[] temp = new int[n];
for(right = 0; right < n; right++) {
temp[left++] = arr[right];
// 提前结束
if(left >= n) {
break;
}
// 处理0
if(arr[right] == 0) {
temp[left++] = 0;
if(left >= n) {
break;
}
}
}
// copy
System.arraycopy(temp, 0, arr, 0, n);
}
效果
0ms 100%
反思
当然，这种方法我们开辟了新的空间，实际上是不符合题意的。
这就是题目设计的不够开放的问题，可以把原地当做一个额外的限制条件。而不是上来就限定死。
v3-双指针
思路
其实这一题是比较难的，双指针拐了2次弯儿，一般人10分钟内估计根本想不到。
就算想到了用 left、right 两个指针移动，类似于 T26 T27，但是会发现，因为要复写 0，会导致后面的数字被覆盖，这个和移除是不同的。
那么，怎么解决呢？
逆流而上
最核心的问题在于直接 0 复制，会导致后面的信息被覆盖。
所以我们最好是从后往前操作。
自然地，我们可以想到快慢指针，先找到结束的位置。然后倒过来处理一遍。
不过做的时候发现好多坑…
实现
错误的解法1
比如下面的解法，虽然考虑到了最后一个数字可能为0.是否需要重复的标识。
public static void duplicateZeros(int[] arr) {
int n = arr.length;
// 通过快慢指针，找到结束时 left 指针的位置。
// 同时记录最后一个 0 是否需要复制
boolean lastZeroRepeatFlag = true;
int totalCount = 0;
int left = 0;
for(int i = 0; i < n; i++) {
left++;
totalCount++;
if(totalCount >= n) {
break;
}
if(arr[i] == 0) {
totalCount++;
// 如果最后一个0是因为刚好0复写变满了，那么则不需要复制。
if(totalCount >= n) {
lastZeroRepeatFlag = false;
break;
}
}
}
// 从哪里开始写
// 从后往前，最后一个位置开始
int i = n-1;
int leftIx = left - 1;
while (i >= 0 && leftIx >= 0) {
// 当前位置
arr[i--] = arr[leftIx];
// 当前位置是0
if(arr[leftIx] == 0 && i > 0) {
// 两个场景需要复制 0
//a. 不是最后一个0
//b. 最后一个0 lastZeroRepeatFlag=true
if(leftIx != (left-1)
|| (leftIx == left-1 && lastZeroRepeatFlag)) {
arr[i--] = 0;
}
}
leftIx--;
}
}
但是在测试用例
输入 arr = [8,4,5,0,0,0,0,7]
输出 [0,0,0,0,0,0,0,0]
预期结果 [8,4,5,0,0,0,0,0]
这个用例却过不去。
正确解法
这里还是看了三叶的解法，很优秀。
这种写法真的很优雅。
实现如下：
public static void duplicateZeros(int[] arr) {
int n = arr.length;
// 慢指针
int i = 0;
// 快指针，包含复写0的数据
int j = 0;
// 这个跳出写法，比我的优雅很多
while (j < n) {
if(arr[i] == 0) {
j++;
}
i++;
j++;
}
// 此时，位置实际上在预期的后面一位
i--;
j--;
//2.从尾到头进行双指针赋值 i : i->slow j : n->fast
while (i >= 0) {
// j最后一步可能执行了+2操作,在此确保j的坐标小于n
if(j < n) {
arr[j] = arr[i];
}
//判断是否需要复写0
if(arr[i] == 0 && j > 0) {
arr[--j] = 0;
}
// 同时左移
i--;
j--;
}
}
反思
虽然看出来是双指针，但是无可奈何，依然没有写对。
有进步，但是还不够。
加油！
数组基本知识+技巧
| 分类 | 代表技巧 |
|---|---|
| 遍历类 | 遍历、双指针、滑窗 |
| 前缀/差分类 | 前缀和、差分、后缀数组 |
| 查找类 | 二分、哈希、离散化 |
| 空间/状态优化 | 状压、滚动数组、差分压缩 |
| 排序/归并类 | 排序、归并逆序对、树状数组、线段树 |
| 子数组/序列 | 动规、中心扩展、单调栈 |
| 矩阵类 | 二维差分、DFS/BFS、旋转模拟 |
| 特殊技巧 | 快速幂、滚动哈希、模拟题技巧 |
🎯 常见遍历技巧 + 力扣题目对照表
| 技巧 | 力扣题目 | 说明 |
|---|---|---|
| 基础遍历 | 27.移除元素 | 直接遍历+判断 |
| 快慢指针 | 26. 删除重复项 | 原地去重 |
| 左右夹逼 | 167.两数之和 II | 排序+夹逼 |
| 滑动窗口 | 209. 长度最小子数组 | 动态控制窗口 |
| 子数组枚举 | 560. 和为K的子数组 | 前缀和优化 |
| 子序列枚举 | 491. 递增子序列 | 回溯 |
| 倒序遍历 | 198. 打家劫舍 | 动态规划 |
| 规则模拟 | 54. 螺旋矩阵 | 控制方向循环遍历 |
