【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-Arrays(数组)
前言
【从蛋壳到满天飞】JAVA 数据结构解析和算法实现，全部文章大概的内容如下：
Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜索树)、Set(集合)、Map(映射)、Heap(堆)、PriorityQueue(优先队列)、SegmentTree(线段树)、Trie(字典树)、UnionFind(并查集)、AVLTree(AVL 平衡树)、RedBlackTree(红黑平衡树)、HashTable(哈希表)
源代码有三个：ES6（单个单个的 class 类型的 js 文件） | JS + HTML（一个 js 配合一个 html）| JAVA (一个一个的工程)
全部源代码已上传 github， 点击我吧 ，光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。
本文章适合 对数据结构想了解并且感兴趣的人群，文章风格一如既往如此，就觉得手机上看起来比较方便，这样显得比较有条理，整理这些笔记加源码，时间跨度也算将近半年时间了，希望对想学习数据结构的人或者正在学习数据结构的人群有帮助。
java 中的数组
数组基础
-
把数据码成一排进行存放
数组名[索引]
-
java 中的数组是有局限性的。
public class Main { public static void main(String[] args) { // 输出 System.out.println("Array"); // 定义数组 int[] arr = new int[10]; // 循环赋值 for (int i = 0; i < arr.length; i++) { arr[i] = i; } // 定义数组 int[] scores = new int[]{100, 99, 88}; // for循环遍历 数组 for (int i = 0; i < scores.length ; i++) { System.out.println(scores[i]); } // 修改数组中某个元素 scores[0] = 60; // foreach 遍历数组 for (int score: scores) { System.out.println(score); } } }
二次封装数组
-
数组的索引可以有语意也可以没有语意。
- 如
scores[2]代表一个班级中第三个学生。
- 如
-
数组的最大优点
- 快速查询，如
scores[2]
- 快速查询，如
-
数组最好应用于“索引有语意”的情况。
- 如果索引没有语意的话，
- 那么使用别的数据结构那会是一个更好的选择。
-
计算机处理的问题有千千万万个
arr[110103198512112312]
-
数组也可以处理“索引没有语意”的情况。
- 在索引有语意的情况下使用数组非常简单，
- 直接就可以查到相应的数据。
- 在索引没有语义的情况下使用数组，
- 那么就会产生很多新的问题。
- 因为这个时候数组只是一个待存
- 放那些要考察的数据的空间，
- 例如你开辟了 8 个元素的空间，
- 但是你只考察 2 个元素，
- 此时就有问题了，剩下的空间都没有元素，
- 可能访问剩下的空间就是非法的，
- 因为从用户的角度上来看是没有那么多元素的，
- 只有两个元素。
-
索引没有语意，如何表示没有元素？
- 如何添加元素？如何删除元素？
- 等等更多问题，
- 例如添加元素时，
- 因为数组创建的时候数组的大小就固定了。
- 在 java 中数组没有这些功能，
- 所以需要基于 Java 的数组，
- 二次封装属于我们自己的数组类。
- 也就是将原本的静态数据变成动态的数组。
将数组封装成自己的数组
-
将原本 Java 中的数组封装到一个类中，
- 从而封装一个属于自己的数组，这个类就叫做 MyArray，
- 在这个类中封装一个 java 的数组，这个数组叫做 data，
- 对这个数组进行增删改插等等的功能。
-
数据结构的本质也是存储数据，
- 之后再进行高效的对这些数据进行操作，
- 只不过你设计的数据结构会把这些数据存储在内存中，
- 所以针对这些数据结构的所添加的操作在大的类别的划分上，
- 也是增删改查。
-
针对不同的数据结构，
- 对应的增删改查的方式是截然不同的，
- 甚至某些数据结构会忽略掉增删改查中的某一个操作，
- 但是增删改查可以作为研究某一个数据结构的相应的脉络，
-
数组本身是静态的，必须在创建的时候指定他的大小，
- 可以把这个容量叫做 capacity，
- 也就是数组空间最多可以装多少个元素，
- 数组空间最多可以装多少个元素与
- 数组中实际装多少个元素是没有关系的，
- 因为这是两回事儿，
- 数组中实际能够装多少个元素可以叫做 size，
- 通过它来控制，在初始化的时候，
- 数组中一个元素都没有，所以 size 为 0，
- 这个 size 相当于数组中第一个没有盛放元素的相应索引，
- 增加数组元素和删除数组元素的时候就要维护这个 size。
-
代码示例
(class: MyArray)public class MyArray { private int [] data; private int size; // 构造函数，传入数组的容量capacity构造Array public MyArray (int capacity) { data = new int[capacity]; size = 0; } // 无参数的构造函数，默认数组的容量capacity=10 public MyArray () { // this( capacity: 10); this(10); } // 获取数组中的元素实际个数 public int getSize () { return size; } // 获取数组的总容量 public int getCapacity () { return data.length; } // 返回数组是否为空 public boolean isEmpty () { return size == 0; } }
对自己的数组进行添加操作
-
向数组添加元素最简单的形式
- 就是在数组的末尾添加一个元素，
- size 这个变量其实就是指向数组中的末尾，
- 添加完元素之后其实也需要维护这个 size，
- 因为数组中的元素多了一个，所以要让它加加。
-
如果是给元素进行插入的操作
- 那么要先判数组的容量是否已经装满了，
- 然后再判断索引是否小于 0 或者大于 size，
- 都没有问题了，就可以根据索引来进行插入了，
- 插入的原理就是那个索引位置及其后的元素，
- 全都都往后移动一位，所以循环是从后往前的，
- 最后让该索引处的旧元素被新元素覆盖，
- 但旧元素并没消失，而是位置往后移动了一位，
- 最后要记得维护 size。
-
向数组中添加元素可以复用向数组中插入元素的方法，
- 因为插入元素的方法也是在给数组添加元素，
- 并且插入元素的方法可以在任何位置插入新元素，
- 那么就可以扩展两个方法，
- 一个插入到数组最前面（插入到索引为 0 的位置），
- 一个是插入到数组最后面
- （插入到索引为 数组最后一个元素的索引+1 的位置）。
-
给数组添加元素的时候如果元素为数字（添加时可排序可不排序）
- 那么每一次添加操作时可以给数组中的元素进行排序，
- 排序方式是按照从小到大来进行排序。
- 先判断添加的这个元素大于数组中哪一个元素，
- 然后将那个元素及其后面的所有元素往后移一位，
- 最后将添加的这个元素插入到那个元素后面。
- 先要对数组中的容量进行判断，
- 如果超过了就不添加，并且报错，
- 每次添加之前要判断一下插入的位置，
- 它后面还有没有元素或者这个数组是否为空。
- 记住每次添加操作都要维护 size 这个变量。
代码示例 (class: MyArray)
public class MyArray {
private int [] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public MyArray (int capacity) {
data = new int[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public MyArray () {
// this( capacity: 10);
this(10);
}
// 获取数组中的元素实际个数
public int getSize () {
return size;
}
// 获取数组的总容量
public int getCapacity () {
return data.length;
}
// 返回数组是否为空
public boolean isEmpty () {
return size == 0;
}
// 给数组添加一个新元素
public void add (int e) {
if (size == data.length) {
throw new IllegalArgumentException("add error. Array is full.");
}
data[size] = e;
size++;
}
// 向所有元素后添加一个新元素 （与 add方法功能一样） push
public void addLast (int e) {
// 复用插入元素的方法
insert(size, e);
}
// 在所有元素前添加一个新元素 unshift
public void addFirst (int e) {
insert(0, e);
}
// 在index索引的位置插入一个新元素e
public void insert (int index, int e) {
if (size == data.length) {
throw new IllegalArgumentException("add error. Array is full.");
}
if (index < 0 || index > size) {
throw new IllegalArgumentException(
"insert error. require index < 0 or index > size"
);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
}
对自己的数组进行查询和修改操作
-
如果你要覆盖父类中的方法，记得要加备注
- 如
// @Override: 方法名 日期-开发人员
- 如
-
获取自定义数组中指定索引位置的元素
- 首先要判断索引是否小于 0 或者
- 大于等于 实际元素的个数，都没有问题时，
- 就可以返回索引位置的元素了。
- 用户没有办法去访问那些没有使用的数组空间。
-
修改自动数组中指定索引位置的元素
- 和获取是一样的，要先判断，
- 只能设置已有存在的元素索引位置的元素，
- 用户没有办法去修改那些没有使用的数组空间。
代码示例 (class: MyArray, class: Main)
-
MyArray
public class MyArray { private int [] data; private int size; // 构造函数，传入数组的容量capacity构造Array public MyArray (int capacity) { data = new int[capacity]; size = 0; } // 无参数的构造函数，默认数组的容量capacity=10 public MyArray () { // this( capacity: 10); this(10); } // 获取数组中的元素实际个数 public int getSize () { return size; } // 获取数组的总容量 public int getCapacity () { return data.length; } // 返回数组是否为空 public boolean isEmpty () { return size == 0; } // 给数组添加一个新元素 public void add (int e) { if (size == data.length) { throw new IllegalArgumentException("add error. Array is full."); } data[size] = e; size++; } // 向所有元素后添加一个新元素 （与 add方法功能一样）push public void addLast (int e) { // 复用插入元素的方法 insert(size, e); } // 在所有元素前添加一个新元素 unshift public void addFirst (int e) { insert(0, e); } // 在index索引的位置插入一个新元素e public void insert (int index, int e) { if (size == data.length) { throw new IllegalArgumentException("add error. Array is full."); } if (index < 0 || index > size) { throw new IllegalArgumentException("insert error. require index < 0 or index > size"); } for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = e; size++; } // 获取index索引位置的元素 public int get (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } return data[index]; } // 修改index索引位置的元素为e public void set (int index, int e) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } data[index] = e; } @Override // @Override: 方法名 日期-开发人员 public String toString () { StringBuilder sb = new StringBuilder(); String arrInfo = "Array: size = %d，capacity = %d/n"; sb.append(String.format(arrInfo, size, data.length)); sb.append('['); for (int i = 0; i < size - 1; i ++) { sb.append(data[i]); sb.append(','); } if(!isEmpty()) { sb.append(data[size - 1]); } sb.append(']'); return sb.toString(); } } -
Main
public class Main { public static void main(String[] args) { // write your code here MyArray ma = new MyArray(20); for (int i = 1; i <= 10 ; i++) { ma.add(i); } System.out.println(ma); ma.insert(1, 200); System.out.println(ma); ma.addFirst(-1); System.out.println(ma); ma.addLast(9999); System.out.println(ma); ma.set(5, 8888); System.out.println(ma.get(5)); } }
对自己的数组进行包含、查找、和删除操作
-
继续对自定义的数组增加新功能
- 包含、搜索、删除这三个功能。
-
包含：
- 判断数组中 是否存在这个元素，
- 不存在返回 false。
-
搜索：
- 根据这个元素来进行 索引的获取，
- 找不到返回 非法索引 -1。
-
删除：
- 首先要判断索引的合法性，
- 其次这个操作与插入的操作其实原理类似，
- 只不过是一个反向的过程，
- 指定索引位置的元素其后面的元素的位置
- 全部往前一位，循环时 初始索引为 指定的这个索引，
- 从前往后的不断向前移动，这样被删除的元素就被覆盖了，
- 覆盖之前要保存一下指定索引的元素的值，
- 这个值要作为返回值来进行返回，
- 然后让 size 减减，因为覆盖掉这个元素，
-
由于数组访问会有索引合法性的判断
- 一定要小于 size，于是用户是访问不到 size 位置的元素了，
- 所以 size 位置的元素可以不用去处理它，
- 但你也可以手动的将这个元素值设置为默认值。
-
有了指定索引删除某个元素并返回被删除的这个元素的操作
- 那么就可以扩展出两个方法，
- 和使用插入方法来进行扩展的那两个方法类似，
- 分别是 删除第一个元素和删除最后一个元素，
- 并且返回被删除的元素，
- 删除数组元素时会判断数组索引的合法性，
- 如果数组为空，那么合法性验证就无法通过。
-
根据元素来删除数组中的某个元素
- 首先通过 包含 的那个方法来判断这个元素是否存在，
- 如果元素不存在那就不进行删除操作，也可以报一个异常，
- 如果元素存在，那就根据 搜索 的那个方法来获取这个元素的索引，
- 最后根据 获取到合法索引 来进行元素的删除。
- 其实你可以使用通过 搜索 的那个方法直接返回元素的索引，
- 如果索引合法你就直接删除，
- 如果索引不合法那就不删除然后也可以报一个异常。
-
可以对那些方法进行扩展
- 如 删除数组中所有的指定元素
- 如 找到数组中所有的指定元素的索引
-
关于自定义的数组已经实现了很多功能，
- 但是这个自定义数组还有很多的局限性，
- 在后面会慢慢解决这些局限性，
- 如 这个数组能存放的数据类型不能是任意的数据类型，
- 如果 这个数组的容量是一开始就固定好的，超出就报异常。
代码示例 (class: MyArray, class: Main)
-
MyArray
public class MyArray { private int [] data; private int size; // 构造函数，传入数组的容量capacity构造Array public MyArray (int capacity) { data = new int[capacity]; size = 0; } // 无参数的构造函数，默认数组的容量capacity=10 public MyArray () { // this( capacity: 10); this(10); } // 获取数组中的元素实际个数 public int getSize () { return size; } // 获取数组的总容量 public int getCapacity () { return data.length; } // 返回数组是否为空 public boolean isEmpty () { return size == 0; } // 给数组添加一个新元素 public void add (int e) { if (size == data.length) { throw new IllegalArgumentException("add error. Array is full."); } data[size] = e; size++; } // 向所有元素后添加一个新元素 （与 add方法功能一样） push public void addLast (int e) { // 复用插入元素的方法 insert(size, e); } // 在所有元素前添加一个新元素 unshift public void addFirst (int e) { insert(0, e); } // 在index索引的位置插入一个新元素e public void insert (int index, int e) { if (size == data.length) { throw new IllegalArgumentException("add error. Array is full."); } if (index < 0 || index > size) { throw new IllegalArgumentException("insert error. require index < 0 or index > size"); } for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = e; size++; } // 获取index索引位置的元素 public int get (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } return data[index]; } // 修改index索引位置的元素为e public void set (int index, int e) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } data[index] = e; } // 查找数组中是否有元素e public boolean contain (int e) { for (int i = 0; i < size; i++) { if (data[i] == e) { return true; } } return false; } // 查找数组中元素e所在的索引，如果不存在元素e，则返回-1 public int find (int e) { for (int i = 0; i < size; i++) { if (data[i] == e) { return i; } } return -1; } // 查找数组中所有元素e所在的索引，最后返回存放 所有索引值的 自定义数组 public MyArray findAll (int e) { MyArray ma = new MyArray(20); for (int i = 0; i < size; i++) { if (data[i] == e) { ma.add(i); } } return ma; // int[] result = new int[ma.getSize()]; // for (int i = 0; i < ma.getSize(); i++) { // result[i] = ma.get(i); // } // // return result; } // 从数组中删除第一个元素, 返回删除的元素 public int removeFirst () { return remove(0); } // 从数组中删除最后一个元素, 返回删除的元素 public int removeLast () { return remove(size - 1); } // 从数组中删除第一个元素e public void removeElement (int e) { int index = find(e); if (index != -1) { remove(index); } // if (contain(e)) { // int index = find(e); // remove(index); // } } // 从数组中删除所有元素e public void removeAllElement (int e) { int index = find(e); while (index != -1) { remove(index); index = find(e); } // while (contain(e)) { // removeElement(e); // } } // 从数组中删除index位置的元素, 返回删除的元素 public int remove (int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("get error. index < 0 or index >= size "); } int temp = data[index]; for (int i = index; i < size - 1; i++) { data[i] = data[i + 1]; } // for (int i = index + 1; i < size; i++) { // data[i - 1] = data[i]; // } size --; data[size] = 0; return temp; } @Override // @Override: 方法名 日期-开发人员 public String toString () { StringBuilder sb = new StringBuilder(); String arrInfo = "Array: size = %d，capacity = %d/n"; sb.append(String.format(arrInfo, size, data.length)); sb.append('['); for (int i = 0; i < size - 1; i ++) { sb.append(data[i]); sb.append(','); } if(!isEmpty()) { sb.append(data[size - 1]); } sb.append(']'); return sb.toString(); } } -
Main
public class Main { public static void main(String[] args) { // 创建一个自定义的数组对象 MyArray ma = new MyArray(20); for (int i = 1; i <= 10 ; i++) { ma.add(i); } /* * Array: size = 10，capacity = 20
*/
System.out.println(ma);
ma.insert(1, 200);
/*
* Array: size = 11，capacity = 20
* [1,200,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.addFirst(-1);
/*
* Array: size = 12，capacity = 20
* [-1,1,200,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.addLast(9999);
/*
* Array: size = 13，capacity = 20
* [-1,1,200,2,3,4,5,6,7,8,9,10,9999]
*/
System.out.println(ma);
ma.set(5, 8888);
/*
* 8888
*/
System.out.println(ma.get(5));
/*
* Array: size = 13，capacity = 20
* [-1,1,200,2,3,8888,5,6,7,8,9,10,9999]
* true
* 6
*/
System.out.println(ma);
System.out.println(ma.contain(5));
System.out.println(ma.find(5));
ma.remove(ma.find(5));
/*
* Array: size = 12，capacity = 20
* [-1,1,200,2,3,8888,6,7,8,9,10,9999]
*/
System.out.println(ma);
/*
* -1
* 9999
* Array: size = 10，capacity = 20
* [1,200,2,3,8888,6,7,8,9,10]
*/
System.out.println(ma.removeFirst());
System.out.println(ma.removeLast());
System.out.println(ma);
ma.removeElement(8888);
/*
* Array: size = 9，capacity = 20
* [1,200,2,3,6,7,8,9,10]
*/
System.out.println(ma);
ma.add(123456);
ma.add(123456);
ma.add(123456);
/*
* Array: size = 3，capacity = 20
* [9,10,11]
* Array: size = 12，capacity = 20
* [1,200,2,3,6,7,8,9,10,123456,123456,123456]
*/
System.out.println(ma.findAll(123456));
System.out.println(ma);
ma.removeAllElement(123456);
/*
* Array: size = 9，capacity = 20
* [1,200,2,3,6,7,8,9,10]
*/
System.out.println(ma);
}
}
## 让自己的数组可存放任何数据类类型 1. 泛型技术可以让数据结构放置“任何”数据类型 2. 在 Java 中泛型的类型不可以是基本数据类型 1. 只能是类类型，也就是说只能存放对象， 2. 不可以存放基本数据类型的值。 3. 在 java 语言中有八种数据基本数据类型 1. boolean、byte、char、short、 2. int、long、float、double。 4. 每个基本数据类型都有对应的包装类 1. 这样就把不是类对象这样的数据变成类对象， 2. Boolean、Byte、Char、Short、 3. Int、Long、Float、Double， 4. 名字完全一样，只不过首字母进行了大写， 5. 这些包装类与他们对应的基本数据类型之间可以无缝的进行转换 1. 这个自动的转换过程就叫作自动的加包或者解包， 2. 也就是基本类型在需要的时候会自动转换为他所对应的包装类， 3. 而这些包装类也会在他们需要的时候自动的转换为 4. 他们所对的基本类型，这样一来就可以将一个数组变成 5. 一个可以放置任何数据类型的泛型数组。 6. 通过在自定义的数组类型后面加上`<E>` 1. E 表示一个任意的类型， 2. 而`<>`表示这个类型拥有了泛型的能力， 3. 在你具体使用的时候可以将`<>`中的 E 4. 改成你想要存放的数据的类型。 7. 泛型这个能力并不是 Java 一开始就有的， 1. 是从 Java1.5 才开始支持的， 2. 在如果在定义的类中使用这个任意类型 E， 3. 需要绕一个弯子，将使用到 E 的地方改成 Object， 4. Object 类是任意类的父类， 5. 然后再对这个类的对象进行强制类型的转换， 6. 如`(E[])new Object[capacity]`， 7. 这样的语法是合法的，这样就相当于在这个类中 8. new 出来一个还没有指定类型的 E 类型的数组， 9. 当你在使用这个类的时候，那么 E 可以变成任意的类型。 8. 比较泛型 E 类型的对象时不能再用`==` 1. 值比较 用 `==`， 2. 引用比较 用 `equals()` 9. 在删除操作时 1. java 中有一个垃圾回收机制， 2. 但是如果引用一直存在的话， 3. 就不会回收，所以可以在删除操作时， 4. 给这个数组 size 位置的元素赋值为 null， 5. 这样相当于就给元素设置默认值 null 了。 10. loitering objects != memory leak 11. 闲置的对象并不等于内存泄漏， 12. 只不过是这个对象没有用了， 13. 还是在这个程序中游荡， 14. 也没有办法被垃圾回收机制回收掉， 15. 但是为了程序优化， 16. 可以手动的把这个闲置的对象去除掉那就更好。 17. 泛型可以存放所有的数据类型 18. 非常的方便，原理还是编译时的代码检查， 19. 最终会编译成具体的数据类型， 20. 或者原理是泛型中存放的数据类型会被编译成新的类型。 ### 代码示例`(class: MyArray, class: Main, class: Student)` 1. Myarray
public class MyArray<E> {
private E [] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public MyArray (int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public MyArray () {
// this( capacity: 10);
this(10);
}
// 获取数组中的元素实际个数
public int getSize () {
return size;
}
// 获取数组的总容量
public int getCapacity () {
return data.length;
}
// 返回数组是否为空
public boolean isEmpty () {
return size == 0;
}
// 给数组添加一个新元素
public void add (E e) {
if (size == data.length) {
throw new IllegalArgumentException("add error. Array is full.");
}
data[size] = e;
size++;
}
// 向所有元素后添加一个新元素 （与 add方法功能一样） push
public void addLast (E e) {
// 复用插入元素的方法
insert(size, e);
}
// 在所有元素前添加一个新元素 unshift
public void addFirst (E e) {
insert(0, e);
}
// 在index索引的位置插入一个新元素e
public void insert (int index, E e) {
if (size == data.length) {
throw new IllegalArgumentException("add error. Array is full.");
}
if (index < 0 || index > size) {
throw new IllegalArgumentException("insert error. require index < 0 or index > size");
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
// 获取index索引位置的元素
public E get (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
return data[index];
}
// 修改index索引位置的元素为e
public void set (int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contain (E e) {
for (int i = 0; i < size; i++) {
// if (data[i] == e) { // 值比较 用 ==
if (data[i].equals(e)) { // 引用比较 用 equals()
return true;
}
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find (E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
// 查找数组中所有元素e所在的索引，最后返回存放 所有索引值的 自定义数组
public MyArray findAll (E e) {
MyArray ma = new MyArray(20);
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
ma.add(i);
}
}
return ma;
// int[] result = new int[ma.getSize()];
// for (int i = 0; i < ma.getSize(); i++) {
// result[i] = ma.get(i);
// }
//
// return result;
}
// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst () {
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast () {
return remove(size - 1);
}
// 从数组中删除第一个元素e
public void removeElement (E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
// if (contain(e)) {
// int index = find(e);
// remove(index);
// }
}
// 从数组中删除所有元素e
public void removeAllElement (E e) {
int index = find(e);
while (index != -1) {
remove(index);
index = find(e);
}
// while (contain(e)) {
// removeElement(e);
// }
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
E temp = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
// for (int i = index + 1; i < size; i++) {
// data[i - 1] = data[i];
// }
size --;
// data[size] = 0;
data[size] = null;
return temp;
}
@Override
// @Override: 方法名 日期-开发人员
public String toString () {
StringBuilder sb = new StringBuilder();
String arrInfo = "Array: size = %d，capacity = %d/n";
sb.append(String.format(arrInfo, size, data.length));
sb.append('[');
for (int i = 0; i < size - 1; i ++) {
sb.append(data[i]);
sb.append(',');
}
if(!isEmpty()) {
sb.append(data[size - 1]);
}
sb.append(']');
return sb.toString();
}
}
2. Main
public class Main {
public static void main(String[] args) {
// 创建一个自定义的数组对象
MyArray<Integer> ma = new MyArray<Integer>(20);
for (int i = 1; i <= 10 ; i++) {
ma.add(i);
}
/*
* Array: size = 10，capacity = 20
* [1,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.insert(1, 200);
/*
* Array: size = 11，capacity = 20
* [1,200,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.addFirst(-1);
/*
* Array: size = 12，capacity = 20
* [-1,1,200,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.addLast(9999);
/*
* Array: size = 13，capacity = 20
* [-1,1,200,2,3,4,5,6,7,8,9,10,9999]
*/
System.out.println(ma);
ma.set(5, 8888);
/*
* 8888
*/
System.out.println(ma.get(5));
/*
* Array: size = 13，capacity = 20
* [-1,1,200,2,3,8888,5,6,7,8,9,10,9999]
* true
* 6
*/
System.out.println(ma);
System.out.println(ma.contain(5));
System.out.println(ma.find(5));
ma.remove(ma.find(5));
/*
* Array: size = 12，capacity = 20
* [-1,1,200,2,3,8888,6,7,8,9,10,9999]
*/
System.out.println(ma);
/*
* -1
* 9999
* Array: size = 10，capacity = 20
* [1,200,2,3,8888,6,7,8,9,10]
*/
System.out.println(ma.removeFirst());
System.out.println(ma.removeLast());
System.out.println(ma);
ma.removeElement(8888);
/*
* Array: size = 9，capacity = 20
* [1,200,2,3,6,7,8,9,10]
*/
System.out.println(ma);
ma.add(123456);
ma.add(123456);
ma.add(123456);
/*
* Array: size = 3，capacity = 20
* [9,10,11]
* Array: size = 12，capacity = 20
* [1,200,2,3,6,7,8,9,10,123456,123456,123456]
*/
System.out.println(ma.findAll(123456));
System.out.println(ma);
ma.removeAllElement(123456);
/*
* Array: size = 9，capacity = 20
* [1,200,2,3,6,7,8,9,10]
*/
System.out.println(ma);
}
}
3. Student
public class Student {
private String name;
private int score;
public Student(String studentName, int studentScore){
name = studentName;
score = studentScore;
}
@Override
// @Override 方法名 日期-开发人员
public String toString(){
return String.format("Student(name: %s, score: %d)", name, score);
}
// 增加入口方法，就可以直接执行代码了
public static void main(String[] args) {
MyArray<Student> arr = new MyArray<Student>();
arr.addLast(new Student("Alice", 100));
arr.addLast(new Student("Bob", 66));
arr.addLast(new Student("Charlie", 88));
System.out.println(arr);
}
}
## 让自己的数组成为动态数组 1. 自定义数组的局限性还有容量为固定的大小， 1. 因为内部还是使用的 java 的静态数组， 2. 静态数组的容量从定义开始就是固定的， 3. 如果一开始就把容量开的太大了， 4. 那么就会浪费很多的空间， 5. 如果容量开的太小了， 6. 那就可能存放的空间不够用。 2. 使用一种解决方案，让自定义数据的容量可伸缩 1. 让自定义数组变成一个动态的数组， 2. 当自定义数组中的空间已经满了， 3. 那就创建一个新的数组， 4. 这个数组的容量定义为原来的容量的两倍， 5. 然后将旧数组中的元素全部放到新数组中， 6. 以循环的方式放入新数组中。 3. 让新数组替代掉旧数组， 1. 当`size == capcity`时创建新数组，容量翻倍， 2. 当`size == capcity / 2`时创建新数组，容量缩小一倍， 3. 最终都会让新数组替代掉旧数组。 4. 使用这种方式会让整体性能上很有优势。 5. 在 Java 的动态数组中选择是扩容倍数是 1.5， 6. 然后无论是 1.5 还是 2 或者 3 都是可以的， 7. 只不过是一个参数的选择， 8. 你可以根据使用场景来进行扩容。 4. 自定义数组的这些操作及性能需要分析。 1. 也就是要进行一个时间复杂度的分析。 ### 代码示例`(class: MyArray, class: Main)` 1. Myarray
public class MyArray<E> {
private E [] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public MyArray (int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public MyArray () {
// this( capacity: 10);
this(10);
}
// 获取数组中的元素实际个数
public int getSize () {
return size;
}
// 获取数组的总容量
public int getCapacity () {
return data.length;
}
// 返回数组是否为空
public boolean isEmpty () {
return size == 0;
}
// 重新给数组扩容
private void resize (int newCapacity) {
E[] newData = (E[])new Object[newCapacity];
int index = size - 1;
while (index > -1) {
newData[index] = get(index);
index --;
}
data = newData;
}
// 给数组添加一个新元素
public void add (E e) {
if (size == data.length) {
// throw new IllegalArgumentException("add error. Array is full.");
resize(2 * data.length);
}
data[size] = e;
size++;
}
// 向所有元素后添加一个新元素 （与 add方法功能一样） push
public void addLast (E e) {
// 复用插入元素的方法
insert(size, e);
}
// 在所有元素前添加一个新元素 unshift
public void addFirst (E e) {
insert(0, e);
}
// 在index索引的位置插入一个新元素e
public void insert (int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("insert error. require index < 0 or index > size");
}
if (size == data.length) {
// throw new IllegalArgumentException("add error. Array is full.");
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
// 获取index索引位置的元素
public E get (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
return data[index];
}
// 修改index索引位置的元素为e
public void set (int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contain (E e) {
for (int i = 0; i < size; i++) {
// if (data[i] == e) { // 值比较 用 ==
if (data[i].equals(e)) { // 引用比较 用 equals()
return true;
}
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find (E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
// 查找数组中所有元素e所在的索引，最后返回存放 所有索引值的 自定义数组
public MyArray findAll (E e) {
MyArray ma = new MyArray(20);
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
ma.add(i);
}
}
return ma;
// int[] result = new int[ma.getSize()];
// for (int i = 0; i < ma.getSize(); i++) {
// result[i] = ma.get(i);
// }
//
// return result;
}
// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst () {
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast () {
return remove(size - 1);
}
// 从数组中删除第一个元素e
public void removeElement (E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
// if (contain(e)) {
// int index = find(e);
// remove(index);
// }
}
// 从数组中删除所有元素e
public void removeAllElement (E e) {
int index = find(e);
while (index != -1) {
remove(index);
index = find(e);
}
// while (contain(e)) {
// removeElement(e);
// }
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
E temp = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
// for (int i = index + 1; i < size; i++) {
// data[i - 1] = data[i];
// }
size --;
// data[size] = 0;
data[size] = null;
if(size == data.length / 2) {
resize(data.length / 2);
}
return temp;
}
@Override
// @Override: 方法名 日期-开发人员
public String toString () {
StringBuilder sb = new StringBuilder();
String arrInfo = "Array: size = %d，capacity = %d/n";
sb.append(String.format(arrInfo, size, data.length));
sb.append('[');
for (int i = 0; i < size - 1; i ++) {
sb.append(data[i]);
sb.append(',');
}
if(!isEmpty()) {
sb.append(data[size - 1]);
}
sb.append(']');
return sb.toString();
}
}
2. Main
public class Main {
public static void main(String[] args) {
// 创建一个自定义的数组对象
MyArray<Integer> ma = new MyArray<Integer>();
for (int i = 1; i <= 10 ; i++) {
ma.add(i);
}
/*
* Array: size = 10，capacity = 10
* [1,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.insert(8, 99999);
/*
* Array: size = 10，capacity = 20
* [1,2,3,4,5,6,7,8,99999,9,10]
*/
System.out.println(ma);
ma.remove(8);
/*
* Array: size = 10，capacity = 10
* [1,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
}
}
## 简单的时间复杂度分析 1. 在算法和数据结构领域有一个非常重要的内容 1. 使用复杂度分析的方式来查看代码相应的性能好不好， 2. 时间复杂度分析是一个理论化的领域， 3. 如果非要非常严谨的去研究它， 4. 那就会涉及到很多数学方面的内容以及很多新概念， 5. 所以只需要对时间复杂度有一个简单的认识即可。 2. 常见的算法的时间复杂度 1. `O(1)、O(n)、O(lgn)、O(nlogn)、O(n^2)`等等 3. 这个大 O 简单的来说描述的是 1. 算法的运行时间和输入数据之间的关系。 2. 如最简单的求和，使用 for 循环来进行求和 3. 他的时间复杂度就是 `O(n)`， 4. 这个 n 表示的是求和 for 循环遍历的次数， 5. 这个算法运行的时间和 for 循环遍历的次数成线性关系， 6. 算法和 n 呈线性关系就是`O(n)`。 4. 为什么要用大 O，为什么要叫做`O(n)`？ 1. 因为忽略掉了很多的常数， 2. 实际时间用线性方程来表示：`T = c1*n + c2`， 3. 其中的 c1 表示循环遍历的每一次的时间， 4. 遍历的次数就为 n， 5. c2 表示遍历之前和之后的代码执行时间， 6. 也就是其它地方的代码执行消耗的时间 7. 如 你要初始化一个变量 sum， 8. 如果你写的是一个方法，你要返回最终结果 sum
public static int calcSum (int[] nums) {
int sum = 0;
for (int num: nums) {sum += num;}
return sum;
}
5. 如果在具体分析算法的时候把 c1 和 c2 也都具体的分析出来， 1. 其实那样没有什么必要，并且在有些情况下也不可能做到， 2. 例如不同的语言实现，执行的时间是不等的， 3. 因为转换为机器码后的指令数也是不一样的， 4. 就算指令都一样，还有不同系统 cpu 执行的操作也是不一样的， 5. 很难判断出来 c1 是几条指令、c2 又是几条指令， 6. 正因为如此所以在分析时间复杂度的时候， 7. 是一定要忽略掉这些常数的， 8. 忽略掉这些常数之后， 9. 算法一：`T = 2*n + 2`、算法二：`T = 2000*n + 10000`， 10. 他们的时候复杂度都是 `O(n)`， 11. 换句话来说他们都是线性时间的算法， 12. 这些算法消耗的时间和输入数据的规模是成一个线性关系。 6. 如果有一个算法三：`T = 1*n*n + 0` 1. 不要认为这个 1 很小、0 也很小， 2. 但是它依然是一个`O(n^2)`级别的一个算法， 3. 也就是说这个算法消耗的时间和这个数据的规模成一个平方关系的， 4. `O(n^2)`要比`O(n)`性能差很多，因为前者是 N 的平方级别的， 5. 虽然第二个算法的常数 2000 和 10000 特别的大， 6. 而第三个算法的常数 1 和 0 特别的小， 7. 的确如此，假设这个 n 为 10， 8. 那么第三个算法消耗的时间会比第二个算法消耗的时间要长， 9. 但是那并不能证明第三个算法比第二个算法性能就要差， 10. 因为这个本来就要分具体情况，常数会影响到执行的时间， 11. 但是计算时间复杂度就是要忽略掉常数的， 12. 因为你实际使用没有办法控制所有常数。 7. 这个 O 其实表示的一个`渐进的时间复杂度` 1. 这个渐进 描述的是当 n 趋近于无穷大的时候， 2. 例如第二个算法与第三个算法中的 n 为 3000， 3. 那么很明显第三个算法肯定要比第二个算法执行时间长， 4. 当这个 n 比 3000 还要大的时候， 5. 那么`O(n^2)`要比`O(n)`的执行时间差的越来越大， 6. 所以当 n 越大，一个低阶算法的性能就越能体现出来， 7. 也就是 n 越大就越能看出来`O(n^2)`要比`O(n)`快。 8. 在实际使用时可能会用到高阶算法 1. 当 n 比较小的时候有可能因为他的常数比较低， 2. 反而可能会快于一个低阶算法， 3. 例如 高阶的排序算法 归并排序、快速排序， 4. 这些高阶排序法都可以对于比较小的数组转而使用插入排序这种方式， 5. 可以很好的进行优化，通常这种优化能获得百分之 10 到百分之 15 性能提升， 6. 它的眼里实际上是插入排序算法的常数要比归并排序、快速排序算法的常数小一些， 7. 这样低阶的算法执行时间要比高阶的算法执行时间要快一些。 9. 大 O 描述的是一个算法或者操作的一个渐进式的时间复杂度， 1. 也就是在说这个算法操作所消耗的时间和输入数据的规模之间的关系 2. 由于大 O 描述的是 n 趋近于无穷大的情况下这个算法的时间复杂度， 3. 所以当出现这种算法时`T = 2*n*n + 300n + 10`， 4. 他的时间复杂度还是`O(n^2)`， 5. 如果这个算法的时间和 n 成 2 次方关系的话， 6. 相应这个算法的时间和 n 成 1 次方的关系会被忽略掉， 7. 因为在这种情况下 低阶项会被忽略掉， 8. 因为当 n 趋近于无穷的时候 低阶项起到的作用太小了， 9. 所以当 n 无穷大的时候低阶项的大小是可以忽略不计的， 10. 所以`T = 2*n*n + 300n + 10`的时间复杂度还是`O(n^2)`。 ### 分析动态数组的时间复杂度 1. 增：O(n) 2. 删：O(n) 3. 改：已知索引 O(1)，未知索引 O(n) 4. 查找：已知索引 O(1)，未知索引 O(n) 5. 其它 1. 未知索引的删除，需要先查后删：O(n^2) 2. 未知索引的删除全部，需要先遍历再查再删：O(n^3) 3. 未置索引的查找全部，需要先遍历：O(n) 6. 所以在使用数组的时候 1. 索引要具有一定语意， 2. 这样就可以直接通过索引来进行操作， 3. 如果索引没有语意， 4. 那么修改和查找会让性能大幅度降低。 7. 增和删如果只对最后一个元素进行操作 1. 那么时间复杂度就为`O(1)`， 2. 但是动态数组要有 resize 伸缩容量的功能， 3. 所以增和删的时间复杂度依然是`O(n)`。 8. 一旦要 resize 了，就需要把整个元素全都复制一遍 1. 复制给一片新的空间， 2. 虽然说 resize 好像是一个性能很差的操作， 3. 但是实际上并不是这样的， 4. 完全使用最坏情况的时间复杂度来分析 resize 是不合理的， 5. 应该使用均摊时间复杂度分析来分析 resize， 6. 其实 resize 所消耗的性能在整体上没有那么的糟糕。 #### 添加操作：时间复杂度为 O(n) 1. `addLast(e)`：向数组末尾添加一个元素 1. 非常简单，只是简单的给`data[size]`赋值， 2. 所以它的时间复杂度为 `O(1)` 3. `O(1)`的时间复杂度表示这个操作所消耗的时间 4. 与 数据的规模是没有关系的， 5. 在分析数组的时间复杂度的时候， 6. 那个时间复杂度与这个数组有多少个元素有关系， 7. 由于你要遍历数组中每一个元素， 8. 那么这个时间复杂度就为`O(n)`（操作 n 个元素）， 9. addLast 都能在常数时间内完成， 10. 所以他的时间复杂度就为`O(1)`（操作 1 个元素）。 2. `addFirst(e)`：向数组头部添加一个元素 1. 需要把数组中的元素都往后移动一个位置， 2. 所以这涉及到遍历数组中每一个元素， 3. 那么这个时间复杂度就为`O(n)`（操作 n 个元素）， 4. 虽然最后也有`O(1)`（操作 1 个元素）的操作 ， 5. 但是在有`O(n)`情况时， 6. 更低阶项`O(1)`会被忽略掉。 3. `insert(index, e)`：在 index 索引这个位置插入一个元素 1. 当 index 为 0 的时候就和`addFirst(e)`一样要向后移动 n 个元素， 2. 当 index 为 size(数组中实际元素个数)的时候就和`addLast(e)`一样 3. 只是简单的给`data[size]`赋值， 4. 由于这个 index 可以取 0 到 size 中任何一个值，有那么多种可能性， 5. 那么就可以进行假设在具体操作的时候取到每一个值的概率都是一样的， 6. 在这种情况下进行操作时它所消耗的时间的期望， 7. 有些情况 index 会小一些，那么向后移动位置的元素会多一些， 8. 有些情况 index 会大一些，那么向后移动位置的元素会少一些， 9. 平均而言这个算法的时间复杂度为`O(n/2)`， 10. 但是这个 2 是一个常数，需要忽略常数， 11. 所以忽略常数后这个算法的时间复杂度为`O(n)` 12. 所以最好的情况下时间复杂就为`O(1)`， 13. 最坏的情况下时间复杂度就为`O(n)`， 14. 中等的情况下时间复杂度就为`O(n/2)`。 4. 添加操作综合来看是一个`O(n)`级别的算法 1. `addLast(e)`：`O(1)`， 2. `addFirst(e)`：`O(n)`， 3. `insert(index, e)`：`O(n/2)=O(n)`。 4. 严格计算就需要一些概率论上的知识， 5. 所以在算法复杂度分析上， 6. 通常关注的是某个算法时间复杂度的最坏情况、最糟糕的情况， 7. 也会有一些特例，但是在现实生活中你不能按照最好的情况去解决问题。 8. 例如 你去上班，公司距离你家的位置最快只需要 5 分钟， 9. 然后你每次去上班只留五分钟的时间从家里出来到公司去， 10. 你这样做就是很高概率的让每次上班都会迟到。 11. 例如 在考试时，考试最好的情况是考满分， 12. 然后你每次都考试都以为自己能考满分的蒙题而不去准备， 13. 你这样做的就是很高概率的让每次考试都会不及格。 14. 在大多数情况下去考虑最好的情况是没有多大意义的， 15. 在算法分析的领域通常会比较严格一些去考察最坏的情况。 5. 在添加操作时，自定义的动态数组容量已满 1. 就会进行 resize 操作，这个 resize 操作显然是`O(n)`， 2. 以为因为要给新数组重新赋值一遍。 #### 删除操作：时间复杂度为 O(n) 1. `removeLast()`：在数组末尾删除一个元素 1. 给末尾的数组元素设置默认值，然后`size--`， 2. 所以它的时间复杂度为 `O(1)` 3. `O(1)`的时间复杂度表示这个操作所消耗的时间 4. 与 数据的规模是没有关系的， 5. 他每次只是操作一个数组元素。 2. `removeFirst()`：在数组头部删除一个元素 1. 需要把数组中的元素都往前移动一个位置， 2. 所以这涉及到遍历数组中每一个元素， 3. 那么这个时间复杂度就为`O(n)`（操作 n 个元素）， 4. 虽然最后也有`O(1)`（操作 1 个元素）的操作 ， 5. 给末尾的数组元素设置默认值，然后`size--`， 6. 但是在有`O(n)`情况时， 7. 更低阶项`O(1)`会被忽略掉。 3. `remove(index)`：删除指定索引位置处的元素并返回 1. 所以最好的情况下时间复杂就为`O(1)`， 2. 最坏的情况下时间复杂度就为`O(n)`， 3. 中等的情况下时间复杂度就为`O(n/2)`， 4. 忽略常数后这个算法的时间复杂度为`O(n)`。 4. 删除操作综合来看是一个`O(n)`级别的算法 1. `removeLast()`：`O(1)`， 2. `removeFirst()`：`O(n)`， 3. `remove(index)`：`O(n/2)=O(n)`。 5. 在删除操作时，自定义的动态数组中实际元素个数为其容量的一半时， 1. 就会进行 resize 操作，这个 resize 操作显然是`O(n)`， 2. 以为因为要给新数组重新赋值一遍。 #### 修改操作：时间复杂度为 O(1) 1. `set(index, e)`：指定索引修改一个元素的值 1. 简单的赋值操作，时间复杂度为`O(1)`。 2. 数组最大的优势就是支持随机访问， 3. 访问到对应索引的值后就可以修改对应索引的值了， 4. 性能超级好。 #### 查询操作：时间复杂度为 O(n) 1. `get(index)`：指定索引查找一个元素的值 1. 简单的获取操作，时间复杂度为`O(1)`。 2. 数组最大的优势就是支持随机访问， 3. 只要知道我要访问的索引是那个数字， 4. 就能够一下子访问到对应索引的值， 5. 性能超级好。 2. `contains(e)`：指定元素来查找，判断元素是否存在 1. 复杂的获取操作，时间复杂度为`O(n)`。 2. 需要遍历整个数组从而找到相同的元素， 3. 这个元素在数组中可能找的到也可能找不到， 4. 所以最好的情况下时间复杂就为`O(1)`，第一个， 5. 最坏的情况下时间复杂度就为`O(n)`，最后一个或者没找到， 6. 中等的情况下时间复杂度就为`O(n/2)`，在中间， 7. 忽略常数后这个算法的时间复杂度为`O(n)`， 8. 分析算法要关注最坏的情况。 3. `find(e)`：指定元素来查找，返回该元素对应的索引 1. 复杂的获取操作，时间复杂度为`O(n)`。 2. 需要遍历整个数组从而找到相同的元素， 3. 这个元素在数组中可能找的到也可能找不到， 4. 所以最好的情况下时间复杂就为`O(1)`，第一个， 5. 最坏的情况下时间复杂度就为`O(n)`，最后一个或者没找到， 6. 中等的情况下时间复杂度就为`O(n/2)`，在中间， 7. 忽略常数后这个算法的时间复杂度为`O(n)`， 8. 分析算法要关注最坏的情况。 #### 其它扩展操作 1. `removeElement(e)`：根据指定元素来进行删除第一相同的元素 1. 首先要进行遍历操作，然后找到指定元素的索引， 2. 最后根据索引来进行删除操作，删除操作中又会进行元素位置移动 3. 于是就有两轮循环了，所以时间复杂度为`O(n^2)`。 2. `removeAll(e)`：：根据指定元素来进行删除所有相同的元素 1. 首先要进行遍历操作，找到一个元素后就删除这个元素， 2. 会复用到`removeElement(e)`，于是有三轮循环了， 3. 所以这个操作是`O(n^3)`。 3. `findAll(e)`：根据指定元素来进行查找，找到所有的元素 1. 首先要进行遍历操作，找到一个元素后就将元素的索引存起来， 2. 所以这个操作是一轮循环，时间复杂度为`O(n)`。 ## 均摊复杂度和防止复杂度的震荡 ### resize 的复杂度分析 1. 不可能每次执行 addLast 操作的时候都会触发 resize 1. 假如数组有十个空间，你执行 addLast 操作操作之后， 2. 只有第十次才会触发 resize，并且数组的容量会翻一倍， 3. 随着你添加的越多，数组的容量会呈现倍数增长， 4. 那么触碰 resize 的概率就越小了， 5. 根本不可能每次添加元素就触发 resize， 6. 所以使用最坏的情况去分析 resize 是非常不合理的。 2. 假设当前的 capacity = 10，并且每次添加操作都使用 addLast 1. 那么在触发 resize 的时候，一共进行了 11 次 addLast 操作 2. 其实一共进行了 21 次基本赋值的操作(10+10+1)， 3. 11 添加操作和十次转移数组元素的操作， 4. 因为 resize 里面会将原数组中的元素赋值给新数组， 5. 所以平均每次 addlast 操作，就约等于进行了 2 次的基本赋值操作。 3. 那可以继续假设 capacity = n，n+1 次 addLast 触发 resize， 1. 总共进行了 2n+1 次基本赋值操作， 2. 这样一来平均来讲 每次 addLast 操作， 3. 都在进行 2 次的基本赋值操作。 4. 相当于就是将 resize 的时间平摊给了 n+1 次 addLast 操作 1. 从而得到一个结论，平均每次 addLast 操作，都会进行 2 次基本操作， 2. 那么 addLast 的时间复杂度不会因为 resize 而变为`O(n)`级别的， 3. 这就意味着 这样的均摊计算，addLast 时间复杂度其实是`O(1)`级别的， 4. 而且他和当前数组中有多少个元素完全没有关系的， 5. 所以在这个例子里，这样的均摊计算比计算最坏情况要更有意义， 6. 这样计算复杂度就叫均摊复杂度， 7. 也就是说 addLast 的均摊复杂度为`O(1)`。 ### 均摊复杂度(amortized time complexity) 1. 均摊复杂度在很多教材中并不会进行介绍， 1. 但是在实际工程中这样的一个思想是很有意义的， 2. 一个相对比较耗时的操作，如果能够保证它不会每次都触发， 3. 那么这个相对比较耗时的操作相应的时间 4. 是可以分摊到其它的操作中来， 5. 其实这样一来，removeLast 操作， 6. 它的均摊复杂度是为`O(1)`的， 7. 虽然它的最坏复杂度是`O(n)`级别的， 8. 但是它的均摊复杂度也是为`O(1)`级别的。 ### 复杂度震荡 1. 同时去看 addLast 和 removeLast 操作时： 1. 如 capacity = n，然后数组容量已经满了， 2. 这时候使用 addLast 操作， 3. 这时候数组就要进行扩容， 4. 那么就会耗费`O(n)`的时间， 5. 这时候又去使用 removeLast 操作， 6. 这时候数组又要进行缩容， 7. 那么又会耗费`O(n)`的时间， 8. 就这样一直的 addLast、removeLast， 9. 那么操作都是在耗费`O(n)`的时间， 2. 这种情况每次都会耗费`O(n)`的复杂度 1. 这就是复杂度的震荡， 2. 明明在均摊的时候是一个`O(1)`的级别， 3. 但是在一些特殊的情况下猛的一下窜到了`O(n)`的级别， 4. 从而产生了这个震荡。 3. 这个震荡发生的原因是： 1. removeLast 时 resize 过于激进(Eager)， 2. 当元素的个数变为容量的二分之一的时候， 3. 立马就让数组进行缩容， 4. 此时整个数组中的元素是满的， 5. 元素的个数和容量是相等的， 6. 然后使用一下 addLast 操作时就又需要扩容了。 4. 解决方案：Lazy 1. 当 removeLast 时进行 resize 不急着进行缩容， 2. 而是等 size 为当前容量的四分之一时再进行缩容， 3. 缩容的大小为原来容量的一半， 4. 这样一来就算立马进行 addLast 操作也不会立马进行扩容操作， 5. 也就是将原来的策略改成了 6. 只有当`size == capcity / 4`时，才将 capacity 减半， 7. 原来是`size == capcity / 2`时，才将 capacity 减半， 8. 通过这样的策略就防止了复杂度的震荡。 9. 要防止容量为 4 时，size 又为 1 时， 10. `data.length / 2 为 0`，那样缩容的容量就为 0 了， 11. 这样一来你任何操作都可能会报异常了。 5. 这种方式其实是非常有意思的方式， 1. 在算法的领域有的时候懒一些 2. 反而让算法最终的整体性能更加好， 3. 所以有时候是在更懒的时候其实是在改善算法性能， 4. 虽然说算法更懒，但是不代表代码更容易编写， 5. 也不代表代码量更少， 6. 有时候让算法更懒，其实代码量会更加的大。 6. 数组背后其实数组这种数据结构背后还有很多东西值得探究， 1. 不要小看数组， 2. 设计一个数据结构整体上就要看它怎么具体的存储数据， 3. 在这个具体的存储的基础上怎样进行数据的增删改查。 #### 代码示例`(class: MyArray, class: Main)` 1. Myarray
public class MyArray<E> {
private E [] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public MyArray (int capacity) {
data = (E[])new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public MyArray () {
// this( capacity: 10);
this(10);
}
// 获取数组中的元素实际个数
public int getSize () {
return size;
}
// 获取数组的总容量
public int getCapacity () {
return data.length;
}
// 返回数组是否为空
public boolean isEmpty () {
return size == 0;
}
// 重新给数组扩容
private void resize (int newCapacity) {
E[] newData = (E[])new Object[newCapacity];
int index = size - 1;
while (index > -1) {
newData[index] = get(index);
index --;
}
data = newData;
}
// 给数组添加一个新元素
public void add (E e) {
if (size == data.length) {
// throw new IllegalArgumentException("add error. Array is full.");
resize(2 * data.length);
}
data[size] = e;
size++;
}
// 向所有元素后添加一个新元素 （与 add方法功能一样） push
public void addLast (E e) {
// 复用插入元素的方法
insert(size, e);
}
// 在所有元素前添加一个新元素 unshift
public void addFirst (E e) {
insert(0, e);
}
// 在index索引的位置插入一个新元素e
public void insert (int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("insert error. require index < 0 or index > size");
}
if (size == data.length) {
// throw new IllegalArgumentException("add error. Array is full.");
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
// 获取index索引位置的元素
public E get (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
return data[index];
}
// 修改index索引位置的元素为e
public void set (int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contain (E e) {
for (int i = 0; i < size; i++) {
// if (data[i] == e) { // 值比较 用 ==
if (data[i].equals(e)) { // 引用比较 用 equals()
return true;
}
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find (E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
// 查找数组中所有元素e所在的索引，最后返回存放 所有索引值的 自定义数组
public MyArray findAll (E e) {
MyArray ma = new MyArray(20);
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
ma.add(i);
}
}
return ma;
// int[] result = new int[ma.getSize()];
// for (int i = 0; i < ma.getSize(); i++) {
// result[i] = ma.get(i);
// }
//
// return result;
}
// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst () {
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast () {
return remove(size - 1);
}
// 从数组中删除第一个元素e
public void removeElement (E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
// if (contain(e)) {
// int index = find(e);
// remove(index);
// }
}
// 从数组中删除所有元素e
public void removeAllElement (E e) {
int index = find(e);
while (index != -1) {
remove(index);
index = find(e);
}
// while (contain(e)) {
// removeElement(e);
// }
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove (int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("get error. index < 0 or index >= size ");
}
E temp = data[index];
for (int i = index; i < size - 1; i++) {
data[i] = data[i + 1];
}
// for (int i = index + 1; i < size; i++) {
// data[i - 1] = data[i];
// }
size --;
// data[size] = 0;
data[size] = null;
// 防止复杂度震荡 防止容量为4，size为1时，data.length / 2 为 0
if(size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return temp;
}
@Override
// @Override: 方法名 日期-开发人员
public String toString () {
StringBuilder sb = new StringBuilder();
String arrInfo = "Array: size = %d，capacity = %d/n";
sb.append(String.format(arrInfo, size, data.length));
sb.append('[');
for (int i = 0; i < size - 1; i ++) {
sb.append(data[i]);
sb.append(',');
}
if(!isEmpty()) {
sb.append(data[size - 1]);
}
sb.append(']');
return sb.toString();
}
}
2. Main
public class Main {
public static void main(String[] args) {
// 创建一个自定义的数组对象
MyArray<Integer> ma = new MyArray<Integer>();
for (int i = 1; i <= 10 ; i++) {
ma.add(i);
}
/*
+ Array: size = 10，capacity = 10
+ [1,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
ma.insert(8, 99999);
/*
+ Array: size = 10，capacity = 20
+ [1,2,3,4,5,6,7,8,99999,9,10]
*/
System.out.println(ma);
ma.remove(8);
/*
+ Array: size = 10，capacity = 20
+ [1,2,3,4,5,6,7,8,9,10]
*/
System.out.println(ma);
for(int i = 1; i <= 5 ; i++) {
ma.remove(1);
}
/*
+ Array: size = 5，capacity = 10
+ [1,7,8,9,10]
*/
System.out.println(ma);
}
}
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
