算法通关村第三关-青铜挑战数组专题

本文主要是介绍算法通关村第三关-青铜挑战数组专题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线性表基础

线性表概念

我们先搞清楚几个基本概念，在很多地方会看到线性结构、线性表这样的表述，那什么是线性结构?与数组、链表等有什么关系?常见的线性结构又有哪些呢?
所谓线性表就是具有相同特征数据元素的一个有限序列，其中所含元素的个数称为线性表的长度，从不同的角度看，线性表可以有不同的分类，例如:
从语言实现的角度
从语言实现的角度顺序表有两种基本实现方式，一体式和分离式，如下 :

图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;}//返回查找元素的位置 , 如果没有返回 -1return -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 ?  "]" :  ",");  }}
}

当然这种是不友好的 , 大家自己用其他方法 …

小结

本关是数组的基础问题，重点是自己实现在数组的首部、中间和尾部插入和删除元素，自己能实现就算通关啦。这个工作看似简单，但是在实现的时候会有大量的坑等着你。

这篇关于算法通关村第三关-青铜挑战数组专题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---