线性表和顺序表

顺序表

1.线性表 

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使
用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表 

2.1概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
储。在数组上完成数据的增删查改。

顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素。

2. 动态顺序表：使用动态开辟的数组存储。

2.1动态顺序表---按需申请

2.2 接口实现 

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空
间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间
大小，所以下面我们实现动态顺序表

对这个动态顺序表进行处理
增删查改
初始化：

检查顺序表空间，如果满了进行增容

顺序表的尾插

 顺序表的尾删

顺序表的头插

顺序表的头删

顺序表的查找

顺序表在pos位置处插入x

顺序表删除pos处的值

顺序表的销毁

顺序表的打印

2.3 顺序表的问题及思考 
问题：
1. 中间 / 头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到
200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间 

2.4 数组相关面试题 
1. 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。
题目：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素
元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

思路：用两个指针进行完成，一个指针往后遍历，只要该数不是val，那么两个指针都往后移动
如果这个数是val，一个指针向后移动，找到不是Val的数，然后赋值给另一个指针，如此循环

2. 删除排序数组中的重复项，要求时间复杂度为O(N)，空间复杂度为O(1)。
题目：
给你一个 非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次 
返回删除后数组的新长度。元素的 相对顺序应该保持一致 。然后返回nums中唯一元素的个数。
更改数组 nums ，使nums的前 k 个元素包含唯一元素，并按照它们最初在 nums中出现的顺序排列
nums的其余元素与nums的大小不重要

思路：用两个下标来完成，一个下标走在最前面，如果两个下标的数字相同，那么就继续往后遍历
如果不相同，那么这个位置的数等于零一个下标下一个位置的数字

3. 合并两个有序数组，要求时间复杂度为O(N)
题目：
给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中
为了应对这种情况，nums1的初始长度为m + n，其中前m个元素表示应合并的元素，
后n个元素为0 应忽略，nums2 的长度为n

思路：第一个数组后面应该留有num2元素个数的空位置，然后从num1的最后开始往前进行两个数组比较
依次放两个数组的最大值在num后面