Algorithms Array（一） —— 题目
将题目分类，总结常用的解题思路
参考图书
- 《算法（第 4 版）》
- 《编程之美》
- 《剑指 Offer（纪念版）》
题目表格
| 题目 | 位置 | 解题思路 | 要点 |
|---|---|---|---|
| 插入排序 | |||
| 希尔排序 | |||
| 快速排序 | |||
| 并归排序 | |||
| 二分查找 | |||
| 数组中只出现一次的数字 | 《剑指 Offer》P211 | 异或 + 分组 | |
| Missing Number | LeetCode 268 | 异或 | |
| 数组中重复的数字 | 《剑指 Offer》P261 | 1. 排序 2. 遍历 + 哈希表 3. 推理 + 重排数组 |
|
| Find All Numbers Disappeared in an Array | LeetCode 448 | 1. 推理 + 重排数组 2. “染色” | |
| 数字在排序数组中出现的次数 | 《剑指 Offer》P204 | 1. 遍历 2. 二分查找 |
|
| 数组中出现次数超过一半的数字 | 《剑指 Offer》P163 | 1. 排序 2. 基于 Partition 函数 3. 所求数字比其他所有数字出现次数之和还要多 |
是否修改输入的数组 |
| 数组中出现次数超过一半的数字 | 《编程之美》P129 | 1. 排序 2.所求数字比其他所有数字出现次数之和还要多 |
|
| 寻找数组中的最大值和最小值 | 《编程之美》P165 | 1. 遍历 2. 分组 3. 分治 |
|
| 快速寻找满足条件的两个数 | 《编程之美》P176 | 1. 穷举 2. 排序 + 二分查找 3. 排序 + 遍历 |
|
| 最小的 K 个数 | 《剑指 Offer》P167 | 1. 排序 2. 基于 Partition 函数 3. 数据容器 + 最大堆 |
|
| 最大的 K 个数 | 《编程之美》P139 | 1. 排序 2. 基于快速排序 3+ TODO |
|
| 构建乘积数组 | 《剑指 Offer》P263 | 画图 | |
| 子数组的最大乘积 | 《编程之美》P180 | 1. 枚举 2. 逻辑推理 |
|
| 子数组的最大和 | 《编程之美》P183 | 1. 枚举 2. 动态规划 |
|
| 连续子数组之和的最大值 | 《剑指 Offer》P171 | 1. 枚举 2. 分析数组的规律 3. 动态规划 |
|
| 连续子数组之和的最大值（二维） | 《编程之美》P189 | TODO | |
| 数组中最长递增子序列 | 《编程之美》P194 | 1. 枚举 2. 动态规划 |
|
| 数组循环移位 | 《编程之美》P199 | 分析题意 | |
| 数组分割 | 《编程之美》P202 | 1. 排序 + 分组 2. 动态规划 |
|
| 二维数组中的查找 | 《剑指 Offer》P38 | 1. 遍历 2. 分析简单例子，寻找普遍规律；分组、剔除； |
|
| 旋转数组的最小数字 | 《剑指 Offer》P66 | 1. 二分查找 2. 双指针找分界点 |
|
| 调整数组顺序使得奇数位于偶数前面 | 《剑指 Offer》P102 | 1. 遍历 2. 双指针交换奇偶数 3. 抽象 “分组逻辑判断” |
|
| 把数组排成最小的数 | 《剑指 Offer》P177 | 抽象 sort 函数的 compare 函数 | |
| 数组中的逆序对 | 《剑指 Offer》P189 | 1. 遍历 2. 分组 + 并归排序 |
以上。