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

线性表基础

线性表概念

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

图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 ?  "]" :  ",");  
        }
    }
}

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

小结

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