本期大纲
- 线性表基础
- 线性表概念
- 数组概念
- 数组的基本操作
- 数组创建和初始化
- 查找一个元素
- 增加一个元素
- 修改一个元素
- 删除一个元素
- 小题一道 - - 单调数组问题
- 小题一道 - - 数组合并问题
- 小结
线性表基础
线性表概念
我们先搞清楚几个基本概念，在很多地方会看到线性结构、线性表这样的表述，那什么是线性结构?与数组、链表等有什么关系?常见的线性结构又有哪些呢?
所谓线性表就是具有相同特征数据元素的一个有限序列，其中所含元素的个数称为线性表的长度，从不同的角度看，线性表可以有不同的分类，例如:
从语言实现的角度
从语言实现的角度顺序表有两种基本实现方式，一体式和分离式，如下 :
图a为一体式结构，存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。这种结构整体性强，易于管理。但是由于数据元素存储区域是表对象的一部分，顺序表创建后，元素存储区就固定了。C和C++都是一体式的结构。图b为分离式结构，表对象里只保存与整个表有关的信息 (即容量和元素个数)，:实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。Java和python是分离式结构
从存储的角度
从存储的角度看，可以分为顺序型和链表型。顺序性就是将数据存放在一段固定的区间内，此时访问元素的效率非常高，但是删除和增加元素代价比较大，如果要扩容只能整体搬迁。
而在链表型里，元素之间是通过地址依次连接的，因此访问时必须从头开始逐步向后找，因此查找效率低，而删除和增加元素非常方便，并且也不需要考虑扩容的问题。链表的常见实现方式又有单链表、循环链表、双向链表等等等.
从访问限制的角度
栈和队列又称为访问受限的线性表，插入和删除受到了限制，只能在固定的位置进行。而Hash比较特殊其内部真正存储数据一般是数组，但是访问是通过映射来实现的，因此大部分材料里并不将Hash归结到线性表中，这里为了学习更紧凑，我们将其与队栈一起学习。线性表的知识框架如下:线性表的常见操作有初始化、求表长、增删改查等，事实上每种数据结构都至少要有这几种操作，大部分的基础算法题都是基于此扩展的。
数组概念
什么是数组?
数组是线性表最基本的结构，对应的英文是array，相互之间不需要记录彼此的关系就能访问 , 是有限个相同类型的变量所组成的有序集合，数组中的每一个变量被称为元素。数组是最为简单、最为常用的数据结构。
以整型数组为例，数组的存储形式如下图所示。
数组有两个要注意的点 :
1.第一个存元素的位置是a[0]，最后一个是a[length-1]
2.数组中的元素在内存中是连续存储的，且每个元素占用相同大小的内存。
数组的基本操作
数组大部分情况下都是int类型的，所以我们就用int类型来实现这些基本功能 .
数组创建和初始化
创建 :
int[] arr = new int[100];
赋值:
初始化数组最基本的方式是循环赋值:
for(int i = 0 ; i < arr.length ; i ++)
arr[i] = i;
也可以这么赋值 :
int[] arr = new int[](1,2,3,5,6,8);
int[] nums = {2, 5, , 4, 6, -10};
查找一个元素
很多题目本质就是查找问题，而数组是查找的最佳载体。基本实现如下:
//查找元素
public static int findSum(int[] arr,int size,int k){
for(int i=0; i < size; i++){
if(arr[i] == k)
return i;
}
//返回查找元素的位置 , 如果没有返回 -1
return -1;
}
增加一个元素
增加和删除元素是数组最基本的操作，看别人的代码非常容易，但是自己写的时候经常bug满天飞。能准确处理游标和边界等情况是数组算法题最基础重要的问题之一。所以务必自己亲手能写一个才可以，不要感觉挺简单就不写，其中涉及的问题在所有与数组有关的算法题中都会遇到。
在介绍插入数组元素的操作之前，我们需要补充一个概念，那就是数组的实际 元素数量有可能小于数组的长度，例如下面的情形。
因此，插入数组元素的操作存在3种情况。
- 尾部插入
- 中间插入
- 超范围插入
尾部插入，是最简单的情况，直接把插入的元素放在数组尾部的空闲位置即
可，等同于更新元素的操作。
中间插入，稍微复杂一些。由于数组的每一个元素都有其固定下标，所以不得不首先把插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放到对应的数组位置上。
插入操作的完整实现代码如下：
package src.sl.test;
/**
* @className: Arr
* @author: TianYuan ShowTime
* @date: 2023/10/26-21:25
**/
public class Arr {
private int[] array;
private int size;
public Arr(int capacity) {
this.array = new int[capacity];
size = 0;
}
/**
* 10. * 数组插入元素
* 11. * @param element 插入的元素
* 12. * @param index 插入的位置
* 13.
*/
public void insert(int element, int index) throws Exception {
//判断访问下标是否超出范围
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("超出数组实际元素范围！");
}
//从右向左循环，将元素逐个向右挪1位
for (int i = size - 1; i >= index; i--) {
array[i + 1] = array[i];
//腾出的位置放入新
array[index] = element++;
size++;
}
}
}
修改一个元素
要把数组中某一个元素的值替换为一个新值，也是非常简单的操作。直接利用数组下标，就可以把新值赋给该元素。
int[] array = new int[]{3,1,2,5,4,9,7,2};
// 给数组下标为5的元素赋值
array[5] = 10;
// 输出数组中下标为5的元素
System.out.println(array[5]);
删除一个元素
数组的删除操作和插入操作的过程相反，如果删除的元素位于数组中间，其后
的元素都需要向前挪动1位。
public int delete(int index) throws Exception {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("超出数组实际元素范围！");
}
int deletedElement = array[index];
for (int i = index; i < size - 1; i++) {
array[i] = array[i + 1];
}
size--;
return deletedElement;
}
数组的优势和劣势
优势
数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。有一种高效查找元素的算法叫作二分查找，就是利用了数组的这个优势。
劣势
至于数组的劣势，体现在插入和删除元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。
小题一道 - - 单调数组问题
描述 :
如果数组是单调递增或单调递减的，那么它是单调的。
题目 :
LeetCode 896. 单调数列
896.单调数列
分析 :
分析: 如果对于所有i<=j，A[i]<= A[j]，那么数组 A 是单调递增的。如果对于所有i<=j，A[i]>=A[j]，那么数组 A 是单调递减的。所以遍历数组执行这个判定条件就行了，由于有递增和递减两种情况。于是我们执行两次循环就可以了 .
解析 :
class Solution {
public boolean isMonotonic(int[] nums) {
int len = nums.length;
return isAsc(nums,len) || isDesc(nums,len);
}
//升序
public boolean isAsc(int[] nums,int len){
for(int i = 0;i < len -1;i++){
if(nums[i] > nums[i+1]){
return false;
}
}
return true;
}
//降序
public boolean isDesc(int[] nums,int len){
for(int i = 0;i < len -1;i++){
if(nums[i] < nums[i+1]){
return false;
}
}
return true;
}
}
这是最基本的写法 , 大家可以进行改进优化
小题一道 - - 数组合并问题
数组合并就是将两个或者多个有席数组合并成一个新的。这个问题的本身不算难，但是要写的够出彩才口以。还有后面要学的归并排序本身就是多个小数组的合并，所以研究该问题也是为了后面打下基础。
描述 :
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
题目 :
LeetCode 88. 合并两个有序数组 :
88.合并两个有序数组
牛客 NC22 合并两个有序的数组 :
NC22 合并两个有序数组
分析 :
对于有序数组的合并，一种简单的方法是先将B直接合并到A的后面，然后再对A排序，也就是这样:
解析 :
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for(int i = 0 ;i< n ;i++){
nums1[m+i] = nums2[i];
}
Arrays.sort(nums1);
System.out.print("[");
for(int i = 0;i< m+n ; i++){
System.out.print(nums1[i]);
System.out.print(i == m + n - 1 ? "]" : ",");
}
}
}
当然这种是不友好的 , 大家自己用其他方法 …
小结
本关是数组的基础问题，重点是自己实现在数组的首部、中间和尾部插入和删除元素，自己能实现就算通关啦。这个工作看似简单，但是在实现的时候会有大量的坑等着你。
