数据结构与算法java版电子书(数据结构与算法java版书籍) 收藏 0

Day 53: Java数据结构与算法 – 查找算法

说到查找算法，可能大家首先想到的就是在数组中找一个数字。没错，但查找可不止这么简单。在我们的日常开发中，查找无处不在 —— 比如在微信搜索联系人、在淘宝搜索商品，这些都离不开查找算法。今天，我们就来聊聊几种常见的查找算法，看看它们各自的特点和应用场景。

这可能是最简单的查找方法了，就像我们找东西一样，从头到尾一个一个找。虽然简单，但在数据量小的时候，它的简单反而成了优势。

二分查找就像我们玩猜数字游戏一样，每次都猜中间的数，然后根据大小关系缩小范围。不过要注意，二分查找只能用在有序数组上。

插值查找是二分查找的改良版。比如我们要在字典中查找\”张\”字，肯定不会从中间开始找，而是会从前面开始找，这就是插值查找的思想。

跳跃查找就像玩跳房子游戏一样，我们不是一步步走，而是跳着走，等找到大概范围后再细找。

让我们来看一个实际的例子，假设我们在开发一个学生管理系统：

让我们看看这些算法各自的特点：

1. 数据量很小时（n < 100）
2. 直接用顺序查找就好
3. 代码简单，维护成本低
4. 实际运行时间可能比复杂算法更快
5. 数据量适中时（100 ≤ n < 10000）
6. 如果数据有序，用二分查找
7. 如果数据需要频繁更新，考虑用跳跃查找
8. 数据量很大时（n ≥ 10000）
9. 优先考虑二分查找
10. 如果数据分布均匀，可以用插值查找
11. 考虑使用更复杂的数据结构（如哈希表、二叉搜索树）

1. 边界条件的处理
2. 数组为空的情况
3. 只有一个元素的情况
4. 目标值在数组范围之外的情况
5. 性能优化技巧
6. 对于经常查找的数据，可以考虑建立索引
7. 频繁查找的场景，可以考虑缓存结果
8. 大数据量时，考虑并行查找
9. 代码健壮性
10. 添加必要的参数检查
11. 处理好异常情况
12. 写好注释和文档

记住，选择查找算法时要根据实际情况来定。就像选择交通工具一样，去楼下超市没必要开车，但是去外地旅游开车可能是最好的选择。在实际开发中，我们也要根据数据量大小、数据是否有序、查找频率等因素来选择合适的查找算法。

Java数据结构与算法

• 遇到一个实际问题，需要解决两个事情
• 如何将会数据存储在计算机中
• 用什么方法策略解决问题
• 轮子虽然不需要自己造了，但是至少需要知道轮子为什么是圆的

数据项：一个数据元素可以由若干数据项组成】

数据对象：有相同性质的数据元素的集合，是数据的子集

数据结构：是相互之间存在的一种或多种特定关系的数据元素的集合

• 逻辑结构：是指数据对象中元素之间的相互关系
• 集合结构
• 线性结构
• 树状结构
• 图形结构
• 物理结构：是指数据的逻辑结构在计算机中的存储形式
• 顺序存储结构
• 链式存储结构

1. 线性表：零个或多个数据元素的有序序列
2. 队列：只允许在一端插入，而在另一端进行删除操作的线性表
3. 堆栈：栈是限定仅在表尾进行插入和删除操作的线性表
4. 树：树是n个节点的有序集。节点可以像树一样越向叶子节点就没有交集
5. 图论：由顶点的又穷空集合和顶点之间边的集合组成
6. 排序和查找算法：排序是对数据进行顺序排列，查找是在大量数据中寻找我们需要的数据的过程

1. 简单：数组是一种最简单的数据结构
2. 占据连续内存: 数组空间连续，按照申请的顺序存储，但是必须指定数组大小
3. 数组空间效率低：数组中经常有空闲的区域没有得到充分的应用
4. 操作麻烦：数组的增加和删除操作很麻烦

零个或多个元素的有序序列

1. 顺序存储结构(一个萝卜一个坑，美女排队)

1. 链式存储结构(天龙三兄弟)

删除节点：将节点后每个元素往前挪一位

1. ArrayList 是由数组来实现数据存储的
2. ArrayList 基本等同于 Vector，除了 ArrayList 是线程不安全(执行效率高) 看源码，在多线程情况下，不建议使用ArrayList

• 通过数组来保存每个元素

扩展：为什么用transient修饰elementData？

被transient修饰的变量不参与序列化和反序列化。当一个对象被序列化的时候，transient型变量的值不包括在序列化的表示中，然而非transient型的变量是被包括进去的。

elementData不参与默认的序列化和反序列化，不代表没有进行序列化和反序列化 ArrayList在序列化的时候会调用writeObject，直接将size和element写入ObjectOutputStream；反序列化时调用readObject，从ObjectInputStream获取size和element，再恢复到elementData。 不直接用elementData来序列化，而采用上诉的方式来实现序列化是因为elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。

ArrayList的底层操作机制源码分析（重点）

1. ArrayList中维护了一个Object类型的数组 elementData [debug看源码]
2. transient Object[] elementData; //transient 表示瞬间，短暂的，表示该属性不会被序列化
3. 当创建对象的时，如果使用的是无参构造器，则初始elementDate的容量是0 (JDK7是10)
4. 当添加元素时，如果使用的是无参构造器，如果需要扩容，则调用grow方法，否则直接添加元素到合适位置
5. 如果使用的是无参构造器，如果第一次添加，需要扩容的话，则扩容elementData为10，如果需要再次扩容的话，则扩容elementData为1.5倍

• 添加add
• 默认在尾部添加
• /** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
• 调用ensureCapactityInternal方法确保列表中有足够的元素来容纳新元素，不足会进行扩容或重新分配内存空间，再添加元素
• System.arraycopy函数
• src – 源数组。
• srcPos – 源数组中的起始位置。
• dest – 目标数组。
• destPos – 目标数据中的起始位置。
• length – 要复制的数组元素的数量。
• 在特定序号添加元素
• public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size – index); elementData[index] = element; size++; }
• 通过arrayCopy将index的元素移动到index+1的位置，再将新添加的元素放在空出来位置上，size++
• 添加所有addAll
• 默认从尾部添加
• public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; }
• 将新添加的集合先转为array,并记录size，确保容量是否足够后，通过System.arraycopy将新添加的数据复制到数组尾部
• 从指定位置从Collection添加所有
• public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size – index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0;}

如果插入元素数大于index,将index后的元素移到新元素之后，再将新元素从index处开始复制

• 删除remove
• 删除指定索引的元素
• public E remove(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); modCount++; E oldValue = (E) elementData[index]; int numMoved = size – index – 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[—size] = null; // clear to let GC do its work return oldValue; }
• 先判断index是否越界，越界则抛出异常
• 记录原始数据
• 计算位移数
• public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;}
• 改set
• /*** Replaces the element at the specified position in this list with* the specified element.** @param index index of the element to replace* @param element element to be stored at the specified position* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E set(int index, E element) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));E oldValue = (E) elementData[index];elementData[index] = element;return oldValue;}
• 查 get
• public E get(int index) {if (index < 0 || index >= this.size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));if (ArrayList.this.modCount != this.modCount)throw new ConcurrentModificationException();return (E) ArrayList.this.elementData[offset + index];}

Arraylist的继承关系

Isterator 接口 -> 用来快速轮询容器

1. ArrayList的大小是如何自动增加的？
2. add函数
3. 什么情况下使用ArrayList？
4. 优点：尾插效率高，支持随机访问 -> 内部是数组
5. 缺点：中间插入或者删除效率低 -> 需要对后面所有节点进行位移
6. 很少删除或插入节点，需要顺序查找用ArrayList
7. 在索引中ArrayList的增加或者删除某个对象的运行过程？效率很低吗？解释一下为什么？
8. ArrayList如何顺序删节点
9. 迭代器 或 for循环从后往前删
10. ArrayList的遍历方式
11. 迭代器
12. for循环(不能随便用)
13. forEach

作业：

https://leetcode.com/problems/remove-duplicates-from-sorted-array/

https://leetcode.com/problems/search-insert-position/

https://leetcode.com/problems/search-insert-position/

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元还是可以连续的，也可以是不连续的

添加节点

注意顺序：

① p.next = s

② s.next = p.next

为什么是这个顺序，反了会怎样？

s.next = p.next

p.next = s

会导致s.next指向s

删除节点：

p.next = p.next.next

修改节点

p.data = new data();

查询节点

双链表的存储结构单元

双链表的表现形式

增加节点

1: s.next = p.next;

2 p.next.prev = s;

3 s.prev = p;

4 p.next = s;

注意:2和4不能调换位置

删

p.next.prev = p.prev;

p.pre.next = p.next;

源码解析

1. List是一个接口，它继承于Collection接口，它代表着有序的队列
2. AbstractList是一个抽象类，它继承于AbstractCollection。AbstructList实现List接口中处理size(), get(int location) 之外的函数
3. AbstructSequentialList是一个抽象类，它继承于AbstructList。AbstructSequentialList实现了\”链表中，根据index索引值操作链表的全部函数\”
4. ArrayList、LinkedList、Vector、Stack是List的四个实现类

1. ArrayList与LinkedList的区别？

作业：

1. 手写一个单链表，并且实现单链表元素的逆置，（a0, a1,a2,a3,..an）-> (an,an-1,… a1, a0),算法的空间复杂度和时间复杂度经可能低。
2. 手写双向链表， 实现增删改查，同时对比自己的LinkList 和源码Linkedlist的异同点
3. 对比源码Arraylist 和LinkedList 的优缺点

算法题：

https://leetcode.cn/problems/merge-two-sorted-lists/

https://leetcode.c/problems/swap-nodes-in-pairs/

https://leetcode.com/problems/copy-list-with-random-pointer/

• 属性：
• data：记录节点的数据
• next：记录下一个节点

LinkedList类

• list ：保存初始节点
• size：记录链表有多少节点

• 在头部添加节点
• 在添加节点后，将新添加的节点作为初始节点
• public void put(T data) { //传入添加节点的数据Node head = list; Node curNode = new Node(data, list); //创建新节点，其next节点是原首节点list = curNode; //将新添加节点作为首节点size++; //节点数+1}
• 在指定位置添加节点
• public void put(int index, T data) {checkPositionIndex(index);Node cur = list;Node head = list;for (int i = 0; i < index; i++) {head = cur; cur = cur.next;}Node node = new Node(data, cur);head.next = node;size++;}
• 检查索引是否合法
• //检查index是否在链表范围内public void checkPositionIndex(int index) {if (!(index >= 0 && index <= size)) {//若超过，则抛出节点throw new IndexOutOfBoundsException(\”index: \” + index + \”, size: \” + size); }}

• 删除头部节点

CPU缓存：位于CPU与内存之间的临时存储器。解决CPU速度和内存速度之间速度差异问题

1. 内存缓存
2. 预先将数据写到了容器(list, map, set)等数据存储单元中，就是软件内存缓存
3. 数据库缓存
4. 网络缓存

1. FIFO (First In, First Out)
2. LFU (Least Frequently Used)
3. LRU (Least Recently Used) \”喜新厌旧\”

1. 新数据插入到链表头部
2. 当缓存命中(即缓存数据被访问)，数据要移到表头
3. 当链表满的时候，将链表尾部的数据丢弃

队列在线程池中是什么情况

队列的存储结构

队列的基本操作

队列的分类

ThreadPoolExecutor线程池实现类

线程池排队：

假设队列大小为10，corePoolSize为3，maximumPoolSize为6，那么当加入20个任务时，执行的顺序应该是怎样的？

1. 首先执行1、2、3
2. 然后任务4-13被放入队列
3. 这时候队列满了，任务14、15、16会被马上执行
4. 而任务17-20则会抛出异常
5. 最终顺序：1、2、3、14、15、16、4、5、6、7、8、9、10、11、12、13

队列(queue)又叫先进先出表，它是一种运算受限的线程表。

其权限是仅允许在表的一端进行插入和另一端取数据，插入是数据的一端是队尾，取数据的一端是队头

什么是栈？

栈(stack)又名后进先出表，它是一种运算受限的线性表

其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对的，把另一端称为栈底

进栈：入栈或压栈，将新元素放到栈顶 元素的上面，使之成为新的栈顶元素

出栈：退站，将栈顶元素删除掉，使之与其相邻的元素成为新的栈顶元素

Java中的Stack是通过Vector来实现的，这种设计被认为是不良的设计，说说你的看法？

由于Stack继承了Vector，有了很多不符合栈的特性的方法 ，比如add方法

逆波兰表达式是一种利用栈来进行运算的数学表达式

• 9 + （3-1）* 3 + 10 / 2
• 标准四则运算表达式——中缀表达式
• 9 3 1 – 3 * + 10 2 / +
• 计算机采用的——后缀表达式：逆波兰表达式

中缀表达式转为后缀表达式：

1. 从左至右扫描一中缀表达式
2. 若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数栈
3. 若读取的是运算符
1. 该运算符为左括号\”(\”，则直接存入运算符栈堆
2. 该运算符为右括号\”)\”，则输出运算堆栈中的运算符到操作数堆栈，直到遇到左括号为止，此时抛弃该左括号
3. 该运算符为非括号运算符
4. 若运算符为非括号运算符：
1. 若运算符堆栈栈顶的运算符为左括号，则直接存入运算符堆栈
2. 若比运算符堆栈栈顶的运算符优先级高，则直接存入运算符堆栈
3. 若比运算符堆栈栈顶的运算符优先级低或相等，则输出栈顶运算符到操作数堆栈，直至运算符栈栈顶运算符低于(不包括等于)该运算符优先级，或为左括号，并将当前运算符压入运算符堆栈
4. 当表达式读取完后运算符堆栈中尚有运算符时，则依序取出运算符到操作数栈，直到运算符堆栈为空

本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com