数据结构，平时用得最多，接触最多的也是数组，先从数组说起。
数组的概念
什么是数组
一组数据，一秒钟可以申明1000个变量的骚操作。
存储相同的类型，连续的存储空间。
最重要的一点：按下标找元素。
数组是如何实现按下标访问元素的？
我们拿一个长度为5的int 类型数组 int [] arr=new int[5]; 来举例，在下面我画的这个图钟，计算机给数组arr,分配了从2000-2019的连续的内存空间，我们假设首地址是2000。下面就是寻址公式：
arr[i]_address=base_address+i*data_type_size; 因为是int类型，data_type_size大小为4。
这里有一个经常的面试考点：数组和链表的区别，很多同学会答，链表的插入和删除时间复杂度为O(n),数组的查找时间复杂度为o(1)。实际上数组的查找操作时间复杂度不是o(1)。你再好的数组，用二分查找时间复杂度都是o(logn)。正确回答，数组支持随机访问，根据下标的查询时间复杂度为o(1)。
数组的初始化方式
动态初始化：
数组类型[] 数组名 = new 数据类型[数组长度];
静态初始化：
简化格式： 数据类型[] 数组名称 = {值, 值, …}; 完整格式（推荐）: 数据类型[] 数组名称 = new 数据类型[]{值, 值, …};
数组是引用类型
所以下面代码输出多少？
int[] arr1 = new int[5]; int[] arr2 = new int[] { 1, 2, 3, 4, 5 }; arr1 = arr2; arr2[2] = 8; Console.WriteLine(arr1[2]);
数组的优缺点
支持下标索引访问，很多时候，我们的数组下标都是没有语义的，在某些情况可以让他有语义。比如特等奖对应0，奖金1000,1等奖，奖金500类似的，不过语义这个也不是啥场合都适合的，大部分场合都是不适合的。
数组内存连续存储，对CPU的缓存也很友好，性能也会更好。
固定了大小，不支持动态扩容，增加和删除数据比较麻烦。
自己实现一个数组
public class MyArray { //实现自己的数组 private int size; private int defaultCapacity; private int[] data; public MyArray():this(10) { } public MyArray(int defaultCapacity) { this.defaultCapacity = defaultCapacity; this.data = new int[defaultCapacity]; } //添加数据逻辑,并且支持动态扩容 public void add(int ele) { if (size > defaultCapacity / 2) { //自动扩容 defaultCapacity = defaultCapacity + defaultCapacity / 2; int[] newData = new int[defaultCapacity]; Array.Copy(this.data, newData,size); this.data = newData; } this.data[size] = ele; size++; } //打印数组 public void print() { for(int i = 0; i < size; i++) { Console.WriteLine(data[i]); } } //获取元素的中的个数 public int getSize() { return this.size; } //删除元素 public void removeEle(int value) { //删除一个数据 int loc = -1; for(int i = 0; i < size; i++) { if (data[i] == value) { loc = i; break; } } if (loc == -1) { throw new ArgumentException("没有找到要删除的元素"); } for(int i = loc; i < size; i++) { data[i] = data[i + 1]; } data[size-1] = 0; //清空数组 size--; } //删除数据根据索引 public void removeIndex(int index) { if (index < 0 || index > this.size) { throw new ArgumentException("索引不合法"); } //删除数据，数据往前移动 for(int i = index; i < this.size; i++) { this.data[i] = this.data[i + 1]; } this.data[size - 1] = 0; //清空数组 size--; } //获取数组的容量 public int getCapacity(int n) { return this.defaultCapacity; } //返回数组是否为空 public bool isEmpty() { return this.size == 0; } //指定索引位置，添加元素。 public void insert(int index,int e) { //1、是否队满 if (size == data.Length) { throw new ArgumentException("add failed,Array is full"); } //2、index是否合法。 if(index<0 || index > this.size) { throw new ArgumentException("add failed,Required index>0 and index<=size"); } //把数据向后移动 for(int i = this.size; i > index; i--) { this.data[i] = this.data[i-1]; } this.data[index] = e; size++; } //是否包含某个元素 public bool contains(int n) { for(int i = 0; i < size; i++) { if (data[i] == n) { return true; } } return false; } //修改某个元素 public void set(int index,int ele) { if (index < 0 || index >= size) throw new ArgumentException("Set failed. Index is illegal."); this.data[index] = ele; } }
数组的面试题分享
1、实现一个支持动态扩容的数组
2、实现两个有序数组合并为一个有序数组
3、实现一个五子棋盘
4、无序数组，排序去重
5、数组的奇偶调换
6、数组无序且带有下标，排成有序，并输出下标