学代码，从最简单的开始

相关资料：
《数据结构与算法之美》
《剑指Offer》

代码规范

1. 代码命名规范

2. 代码书写规范

1. 合并判断条件，减少 if 语句

if (sortType == SortType.descend)

优化为

if (num > data[i] && sortType == SortType.descend)

总结思路

1. 谨慎处理边界问题（空数组等）

2. 从变化中设计不变的量

• 题目 283 移动零：后移 0 → 前移非 0
• 题目 566 重塑矩阵：index 表示重构矩阵前后的第 index 个元素

3. 类比经典算法

• 题目 03 数组中重复的数字：n 个元素，取值范围为 0~n-1 → 类 Hash 寻找元素冲突
• 题目 04 二维数组中的查找：行和列均递增 → 类二分法缩小查找范围

数据结构与算法之美

1. 数组

题目 1：大小固定的有序数组，支持动态增删改

• 错误 1：插入函数搜索插入位置时 index 初值为 -1，未考虑空数组的情况，导致数组越界

// 考虑空数组，因此 index 设为 0
if (count == 0) {
    index = 0;
}

• 错误 2：降序数组只有元素 7 时，插入 4 的index值为 0，反而插入到了 7 前面，未考虑数组元素比较结束，插入数组末尾的情况

// 考虑插入数组末尾的情况
if (i == count) {
    index = count;
}

查找成功后没有 break 循环，导致此判断条件失效

• 总结：未考虑插入首位和末位的特殊情况（即边界）**

题目 2：支持动态扩容的无序数组，按索引增删改查

1. 无参构造函数调用有参构造函数
2. 数组已满则扩容，不足1/4则缩容为1/2，扩容和缩容调用同一函数

题目 3：两个有序数组合并为一个有序数组

• 错误：数组中有 count 个元素，但最后一个元素的位置是 count-1

剑指Offer

题目 03：数组中重复的数字

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内

• 思路1（×）：HashSet的add方法，元素重复则返回false

• 思路2（√）：将值为 i 的元素调整到第 i 个位置上进行求解（类Hash）

时间复杂度 O(n)，空间复杂度 O(1)

• 注意事项：

1. 某处缺少返回值
2. 先初始化类，才能在main函数中调用

题目 04：二维数组中的查找

行和列均递增

• 思路：选取数组中右上角的数字，缩小查找区间（类似二分法取中值）

时间复杂度 O(M + N)，空间复杂度 O(1)

1. if 该数字=要查找的数字，查找过程结束
2. else if 该数字>要查找的数字，剔除这个数字所在的列
3. else if 该数字<要查找的数字，剔除这个数字所在的行

• 注意事项：

1. 空数组求长度越界
2. 判断空数组的条件写在一起

if (matrix == null || matrix.length == 0 || matrix[0].length == 0)

LeetCode

1. 数组与矩阵

题目 283：移动零

将数组 nums 中的 0 移动至数组末尾

• 思路：遍历数组，跳过 0 元素，即前移非 0 元素，最后根据 index 位置在末尾补 0（移动 0 至末尾 → 移动非 0 至前面）

时间复杂度 O(n)，空间复杂度 O(1)

题目 566：重塑矩阵

将 m×n 的矩阵 nums 重构为 r×c 的矩阵 reshapedNums

• 思路：重构过程中行遍历的元素位置不变，将 index 设为原数组 nums 行遍历的第 index 个元素（index < m×n），则重构后其依然为第 index 个元素

1. 2×2 → 1×4：reshapedNums[i][j] = nums[index / 2][index % 2]
2. 1×6 → 2×3：reshapedNums[i][j] = nums[index / 6][index % 1]
3. m×n → r×c：reshapedNums[i][j] = nums[index / n][index % n]

时间复杂度 O(r * c)，空间复杂度 O(r * c)