【学点数据结构和算法】01-数组
【学点数据结构和算法】01-数组
写在前面： 博主是一名大数据的初学者，昵称来源于《爱丽丝梦游仙境》中的Alice和自己的昵称。作为一名互联网小白，
写博客一方面是为了记录自己的学习历程，一方面是希望能够帮助到很多和自己一样处于起步阶段的萌新。由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！个人小站:http://alices.ibilibili.xyz/ , 博客主页:https://alice.blog.csdn.net/ 尽管当前水平可能不及各位大佬，但我还是希望自己能够做得更好，因为一天的生活就是一生的缩影。我希望在最美的年华，做最好的自己！
先来解释下博主为什么会在这个时候开设一个专栏来学习【数据结构和算法】。
就像各位所知道的，在如今的互联网招聘中，面试官越来越着重考察应聘者的一个基础实力。像数据结构与算法，如果一点没接触，连门槛都进不去(尤其是大厂，不会算法基本没戏)。而博主，作为一个00后，大二的学生，很不幸地在过去一年多时间里几乎没有接触过数据结构和算法。虽然我并不抱着实习就能进大厂的打算，但是从长远的角度出发，早点开始学习数据结构和算法，并非一件坏事。至少等到实力充足了，例如工作了两三年，完全可以通过社招的形式凭本事进大厂。所以在闲暇之余，就自己开设了一个专栏，用于没事的时候写写，就当是为自己补充能量了吧哈哈。
好了，不多哔哔了，在正式开始之前，先奉上一张大佬制作的思维导图(来源：https://www.cnblogs.com/zhanghaodong/p/10281923.html)。可谓总结的非常精辟，而我作为一个入门级选手，决定后面就按着这个路线去学习。
本篇我们先来学习数组。
基本概念
数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式是顺序存储，访问方式是随机访问。利用下标查找数组元素的时间复杂度是O(1)，中间插入，删除数组元素的时间复杂度是O(n)。
特点
- 在内存中，数组是一块连续的区域
- 数组需要预留空间(数组的空间在编译阶段就需要进行确定，所以需要提前给出数组空间的大小),预先申请可能会浪费内存空间，即数组空间利用率低
- 在数组起始位置处，插入数据和删除数据效率低。
- 随机访问效率很高，时间复杂度可以达到O(1)
- 数组开辟的空间，在不够使用的时候需要扩容，扩容的话，就会涉及到需要把旧数组中的所有元素向新数组中搬移
- 数组的空间是从栈分配的
常用操作
插入数据
/**
* 数组插入元素
* @param index 插入的位置
* @param element 插入的元素
*/
public void insert(int index, int element) throws Exception {
//判断访问下标是否超出范围
if(index<0 || index>size){
throw new IndexOutOfBoundsException("超出数组实际元素范围！");
}
//如果实际元素达到数组容量上线，数组扩容
if(size >= array.length){
resize();
}
//从右向左循环，逐个元素向右挪一位。
for(int i=size-1; i>=index; i--){
array[i+1] = array[i];
}
//腾出的位置放入新元素
array[index] = element;
size++;
}数组扩容
/**
* 数组扩容
*/
public void resize(){
int[] arrayNew = new int[array.length*2];
//从旧数组拷贝到新数组
System.arraycopy(array, 0, arrayNew, 0, array.length);
array = arrayNew;
}删除元素
/**
* 数组删除元素
* @param index 删除的位置
*/
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;
}输出数组
/**
* 输出数组
*/
public void output(){
for(int i=0; i<size; i++){
System.out.println(array[i]);
}
}完整代码
public class MyArray {
private int[] array;
private int size;
public MyArray(int capacity){
this.array = new int[capacity];
size = 0;
}
/**
* 数组插入元素
* @param index 插入的位置
* @param element 插入的元素
*/
public void insert(int index, int element) throws Exception {
//判断访问下标是否超出范围
if(index<0 || index>size){
throw new IndexOutOfBoundsException("超出数组实际元素范围！");
}
//如果实际元素达到数组容量上线，数组扩容
if(size >= array.length){
resize();
}
//从右向左循环，逐个元素向右挪一位。
for(int i=size-1; i>=index; i--){
array[i+1] = array[i];
}
//腾出的位置放入新元素
array[index] = element;
size++;
}
/**
* 数组扩容
*/
public void resize(){
int[] arrayNew = new int[array.length*2];
//从旧数组拷贝到新数组
System.arraycopy(array, 0, arrayNew, 0, array.length);
array = arrayNew;
}
/**
* 数组删除元素
* @param index 删除的位置
*/
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;
}
/**
* 输出数组
*/
public void output(){
for(int i=0; i<size; i++){
System.out.println(array[i]);
}
}
public static void main(String[] args) throws Exception {
MyArray myArray = new MyArray(4);
myArray.insert(0,3);
myArray.insert(1,7);
myArray.insert(2,9);
myArray.insert(3,5);
myArray.insert(1,6);
myArray.insert(5,8);
myArray.delete(3);
myArray.output();
}
}本篇博客中代码来源于《漫画算法》 感兴趣的朋友可以去购买正版实体书，确实不错，非常适合小白入门。
总结
数组的优势:
数组拥有非常高效的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。有一种高效查找元素的算法叫作二分查找，就是利用了数组的这个优势。
数组的劣势:
数组的劣势，体现在插入，删除元素方面。由于数组元素连续紧密地存储在内存中，插入、删除元素都会导致大量元素被迫移动，影响效率。
总的来说，数组所适合的是读操作多，写操作少的场景，下一节 我们要讲解的链表则恰恰相反。
如果以上过程中出现了任何的纰漏错误，烦请大佬们指正?
受益的朋友或对大数据技术感兴趣的伙伴记得点赞关注支持一波?
希望我们都能在学习的道路上越走越远?
腾讯云开发者
