数组相关题目

数组类相关题目

搜索旋转排序数组

https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

二分之后，必有一边是有序的(因为全局只有一个间断点，该点只能出现于一侧)。检查target是否坐落于有序一侧，如果不位于有序一侧，则一定位于无序一侧。

target取位于的那一侧继续迭代

缺失的第一个正数

https://leetcode-cn.com/problems/first-missing-positive/

观察可知，题目所求正数不超过数组长度+1

遍历每一个位置，将该位置上的值x与位置x-1上的值y交换，重复交换直到x == y或 x < 0 或 x > 数组长度。

之后继续下一个位置

在排序数组中查找元素的第一个和最后一个位置

https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

寻找左边界和有边界，二分条件大于小于情况照常处理，等于时，如果寻找左边界，则取左区间，反之右区间。

每次mid==target时记录最新的值

循环的s > e 时跳出。

此时的最新mid值即为边界。

最长递增子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/

贪心算法，构建队列，遍历数字，当数字大于队尾，则增加该数字，否则，找到第一个大于该数字的元素，修改为该数字。

通过二分查找加速

sort search会返回最小的满足true条件的位置，否则返回len(list)，注意函数中大于等于条件。

idx := sort.Search(len(list), func(i int) bool {return list[i] >= n})
if idx < len(list) {
    list[idx] = n
}