更新时间： 2019/10/8

本文对剑指Offer & LeetCode在AcWing的题解进行了归类整理，并附上AcWing相关题解链接以及个人思考。

后续题目增多后会整理链接，建立多个文档以便阅读。

一 . 数组

1 . 一维数组 

a . 找出数组中重复的数字

特点：

数组规模为n，数在0 ~ n - 1之间。

解法分析：

负数标记：时间复杂度O(n)  |  空间复杂度O(1)

交换归位：时间复杂度O(n)  |  空间复杂度O(1)

排序：时间复杂度O(nlogn)  |  空间复杂度O(logn)

查表：时间复杂度O(n)  |  空间复杂度O(n)

注意：

* 需要先遍历一遍数组，寻找越界元素。

相似题目：

LeetCode . 442（数组规模为n，数在1 ~ n 之间，需注意下标处理）

b . 不修改数组找出重复的数字

特点：

抽屉原理且不能修改数组元素

解法分析：

抽屉原理二分：时间复杂度O(nlogn)  |  空间复杂度O(1)

快慢指针模拟链表：时间复杂度O(n)  |  空间复杂度O(1)

注意：

* 二分模板参考。

* 快慢指针做法，模拟链表思维独特，题目的特点使得nums[nums[i]]不会越界，并且存在环。

* 如果可以修改数组，有其他时间复杂度O(n)的做法。

c . 旋转数组的最小数字

特点：

去掉尾部重复元素后，已排序的数组的查找问题，考虑二分法。

解法分析：

二分法：时间复杂度O(logn)  |  空间复杂度O(1)

一般查找：时间复杂度O(n)  |  空间复杂度O(1)

注意：

* 数组是否包含重复元素影响到是否可以二分，含有重复元素时首先需要剔除尾部的重复元素。

* 需要考虑数组完全单调的特殊情况。

相似题目：

LeetCode . 153（不包含重复元素）

d . 调整数组顺序使奇数位于偶数前面

特点：

奇数偶数排序问题。

解法分析：

双指针法：时间复杂度O(n)  |  空间复杂度O(1)

申请额外数组：时间复杂度O(n)  |  空间复杂度O(n)

注意：
* 类似快排的思想。

* 注意约束条件处理特殊情况下的数组越界。

2 . 二维数组 

a . 二维数组中的查找

特点：

L型单调。

解法分析：

单调性扫描：时间复杂度O(n + m)  |  空间复杂度O(1)

二分：时间复杂度O(logn + logm)  |  空间复杂度O(1)

注意：

* 二分是查找算法中首先可以考虑的。

* 还要注意数组的单调性。