数组-刷题算法总结篇

数组。最基础的一种数据结构，无论是什么样的算法题，大部分都会涉及到对数组的操作。

如何有效的利用数组，并且在数组上运用各种算法进行题目求解，是我们学习的目标。

常见的基于数组的问题：

排序
二分查找
双指针
滑动窗口
模拟

数组基础

数组不同于链表，标准定义：「数组是存放在连续内存空间上的相同类型数据的集合」

所以，数组的相邻元素的地址是连续的。

同时，可以根据下标来取数组对应位置的值（数组的索引从0开始）。

时间复杂度：

根据下标取元素O（1）
删除下标为x的元素O(n)

Java中可以直接new出一个数组，同时也可以使用ArrayList对象来模拟数组。

一维数组的定义：

二维数组的定义：

排序问题

排序是最常见于面试中的问题，但经常以两种形式出现：

一种是八股文中，考察对排序算法的理解以及复杂度的理解
另一种是考察几种特殊的算法，并且写出代码（常见的比如快排、归并排序等）

这里不再单独列出。

但偶有时候，仅仅需要数组排序结果的时候，可以使用库函数进行排序:

从小到大排序

Arrays.sort(arr);// 默认从小到大排序

自定义排序方式

public class shuzu {
    public static void main(String[] args) {
        Integer[] arr = new Integer[10];
        arr[0] = 10;
        Arrays.sort(arr);
        Arrays.sort(arr, (a,b)->b-a);  //如果自定义排序，arr的类型需要设置为Integer类型
        Arrays.stream(arr).forEach(System.out::println);
    }
}

二分查找

二分查找是数组中比较常见的问题，常见问题类型：

让你求最大的情况下什么最小，或者最小的情况下什么最大

在抽象一下：比如一个数组是有序的，让你求一个元素在这个数组的什么位置；

其实就是动态的缩小范围、排除掉不在答案之外的范围

在解题的过程中，需要明确关注几个点：

左右边界的范围
左右边界变化之后，新的左右边界是否维持之前的含义
什么时候跳出循环

leetcode中常见二分问题：https://leetcode.cn/tag/binary-search/problemset/

easy: 搜索插入位置 https://leetcode.cn/problems/search-insert-position/description/
mid: 寻找峰值 https://leetcode.cn/problems/find-peak-element/description/
hard: 寻找排序数组中的最小值：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/description/

双指针

双指针在解决数组问题或者链表问题中较为常见。

基本特征：能够通过两个指针实现在线性结构上遍历，从而来解决问题。

常见解题方式：

相向而行法：两个指针，一个从左边界移动；一个从右边界移动；两者根据条件的不同，相向而行；到达某一个条件之后，停止移动，得到答案。
快慢指针：两个指针，同时从一个点出发，每循环一次，一个走一步，另一个走两步，从而实现一快一慢。（在链表中：快指针到达终点时，慢指针走到快指针的一半）

leetcode中常见双指针题目：https://leetcode.cn/tag/two-pointers/problemset/