数组-刷题算法总结篇

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

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

常见的基于数组的问题:

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

数组基础

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

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

同时,可以根据下标来取数组对应位置的值(数组的索引从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/

双指针

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

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

常见解题方式:

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

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

滑动窗口

滑动窗口主要解决子数组/子序列的问题

可以理解:窗口是可以动态调整大小的(也就是左右边界)

通过左右边界的调整,可以满足题目的某些条件,从而能够得到最后的答案。比如满足符合条件的最小窗口长度等。

可以将O(n^2)的问题将为O(n)

leetcode中常见滑动窗口题目:https://leetcode.cn/tag/sliding-window/problemset/

模拟

模拟类型的题目,通常就是考察应变能力

主要步骤:题目抽象成模型=>用数组或其他数据结构表示数据=>明白不同状态的转换=>处理边界问题

上面提到的是针对数组的常见问题,后续将会出每个板块的专门讲解。

#笔试##算法##刷题#
25实习秋招刷题专栏-Java 文章被收录于专栏

针对实习秋招的同学,无论你是零基础入门还是已经在刷题的道路上驰骋的同学。在这里,你都能针对性的提高自己的刷题能力,提升自己对算法题的认知。 本专栏目的在于帮助需要帮助的同学顺利拿到实习以及秋招的offer!

全部评论

相关推荐

头像
05-14 12:29
安卓
点赞 评论 收藏
分享
1 收藏 评论
分享
牛客网
牛客企业服务