0%

数据结构:数组

1. 简介

数组是最基本的数据结构,属于线性表。存储一个固定大小的相同类型元素的顺序集合。

最大的优势就是支持随机访问,即知道索引就可以访问。但是数组的长度一旦声明就是固定死的。

接下来来使用数组二次封装实现栈,队列。

2. 二次封装数组

二次封装来实现数组的增删改查。

创建一个泛型类,其中有两个成员属性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Array<E> {
// 泛型数组
private E[] data;
// 目前已存储的元素个数
private int size;

/**
* 有参构造函数
* @param capacity 容量
*/
public Array(int capacity){
data = (E[])new Object[capacity];
size = 0;
}

/**
* 无参构造函数,默认数据容量为10
*/
public Array(){
this(10);
}
}

2.1 添加操作

1
2
3
4
5
6
7
8
9
10
11
/**
* 在数组末尾添加元素
* @param e
*/
public void addLast(E e){
if(size == data.length){
throw new IllegalArgumentException("AddLast failed. Array is full.");
}
data[size] = e;
size++;
}

在指定位置插入值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 在索引位置插入值
* @param index
* @param e
*/
public void add(int index, E e){
if(index < 0 || index > size || size == data.length){
throw new IllegalArgumentException("Add failed. Require index < 0 || index > size");
}
// 把要插入到的位置的元素全部向后移动
// 并且只能从最后一个元素开始后移,不然就会丢失数据
for(int i = size - 1; i >= index; i--){
data[i + 1] = data[i];
}
// 最后再插入
data[index] = e;
size++;
}

此时也可以修改addLast:

1
2
3
4
5
6
7
/**
* 在数组末尾添加元素
* @param e
*/
public void addLast(E e){
add(size, e);
}

可以在数组开头添加:

1
2
3
4
5
6
7
/**
* 在数组开头添加元素
* @param e
*/
public void addFirst(E e){
add(0, e);
}

2.2 查找操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
res.append('[');
for(int i = 0; i < size; i++){
res.append(data[i]);
if(i != size - 1){
res.append(", ");
}
}
res.append(']');
return res.toString();
}

根据索引查询元素:

1
2
3
4
5
6
7
8
9
10
11
/**
* 根据index索引查出该位置的元素
* @param index
* @return
*/
public E get(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Get failed. Index is illegal");
}
return data[index];
}

延伸出查询首元素,和尾元素:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
* 查询首元素
* @return
*/
public E getFirst(){
return get(0);
}

/**
* 查询尾元素
* @return
*/
public E getLast(){
return get(size - 1);
}

其他查询操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 * 查询数组中是否包含元素e
* @param e
* @return
*/
public boolean contains(E e){
for(int i = 0; i < size; i++){
if(data[i].equals(e)){
return true;
}
}
return false;
}

/**
* 查询数组中元素e的所在索引,如果不存在元素e,则返回-1
* @param e
* @return
*/
public int find(E e){
for(int i = 0; i < size; i++){
if(data[i] == e){
return i;
}
}
return -1;
}

2.3 修改操作

1
2
3
4
5
6
7
8
9
10
11
/**
* 修改index索引位置的元素为e
* @param index
* @param e
*/
public void set(int index, E e){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Set failed. Index is illegal");
}
data[index] = e;
}

2.4 删除

删除指定索引的元素的思路:跟指定位置插入的操作相反,在目标索引的后一个索引开始向前移,把目标索引“吃”掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 /**
* 从数组中删除index索引的元素,并返回该删除的元素
* @param index
* @return
*/
public E remove(int index){
if(index < 0 || index >= size){
throw new IllegalArgumentException("Remove failed. Index is illegal");
}
E ret = data[index];
for(int i = index + 1; i < size; i++){
data[i-1] = data[i];
}
size--;
// 使用了泛型,那么里面的元素都是引用,如果删除了元素后,此时data[size]还是指定该引用,
// 根据Java的垃圾回收机制,此时不会释放空间,所以可以自己指定为null,那么该空间就会被回收。
// 当然不一定要有这一步,要是删除后添加一个值,那么该位置会指向一个新的元素。
data[size] = null;

return ret;
}

/**
* 删除数组首元素
* @return
*/
public E removeFirst(){
return remove(0);
}

/**
* 删除数组尾元素
* @return
*/
public E removeLast(){
return remove(size - 1);
}

/**
* 从数组中删除元素e
* @param e
*/
public void removeElement(E e){
int index = find(e);
if(index != -1){
remove(index);
}
}

3. 动态数组

我们知道数组是静态的,也就是长度固定不变,那么动态数组的含义也就可以知道,就是可以动态改变数组长度,现在来添加一个修改长度的方法:

1
2
3
4
5
6
7
8
9
10
11
12
/**
* 修改数组容量,使之成为动态数组
* 实际上并不是真正修改原先的数组长度,而是把原先的数组中的元素复杂到另一个新长度的数组中
* @param newCapacity
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for(int i = 0; i < size; i++){
newData[i] = data[i];
}
data = newData;
}

修改添加操作:在添加元素时,满足一定条件扩容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 在索引位置插入值
* @param index
* @param e
*/
public void add(int index, E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("Add failed. Require index < 0 || index > size");
}
if(size == data.length){
// 扩容,每次扩容本长度的2倍
resize(2 * data.length);
}
// 把元素向后移动
for(int i = size - 1; i >= index; i--){
data[i + 1] = data[i];
}
data[index] = e;
size++;
}

修改删除操作:在删除元素后,满足一定条件缩容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
* 从数组中删除index索引的元素,并返回该删除的元素
* 跟指定位置插入的操作相反,在目标索引的后一个索引开始向前移,把目标索引“吃”掉。
* @param index
* @return
*/
public E remove(int index){
// 这里就不怕容量满了不能添加元素
if(index < 0 || index >= size){
throw new IllegalArgumentException("Remove failed. Index is illegal");
}

E ret = data[index];
for(int i = index + 1; i < size; i++){
data[i-1] = data[i];
}
size--;
// 使用了泛型,那么里面的元素都是引用,如果删除了元素后,此时data[size]还是指定该引用,
// 根据Java的垃圾回收机制,此时不会释放空间,所以可以自己指定为null,那么该空间就会被回收。
// 当然不一定要有这一步,要是删除后添加一个值,那么该位置会指向一个新的元素。
data[size] = null;

// 缩容,如果此时元素个数为总长度的1/4,这里为什么是是1/4,而不是1/2最下面有解释
// data.length / 2防止把长度变成0
if(size == data.length / 4 && data.length / 2 != 0){
resize(data.length / 2);
}
return ret;
}

4. 时间复杂度

4.1 普通数组

对于添加操作的时间复杂度:

  • addLast(e):O(1)
  • addFirst(e):O(n)
  • add(index, e):根据概率论,平均来看,index比较小那么移动就比较多,操作就慢,如果index比较大那么移动就比较少,操作就快,所以可以得平均需要移动n/2的元素:O(n/2) = O(n)

整体的添加操作的时间复杂度就是:O(n)(只关注最坏情况)

对于删除操作的时间复杂度跟添加操作类似,整体的删除操作的时间复杂度就是:O(n)(只关注最坏情况)

对于修改操作的时间复杂度:如果知道索引那么就是O(1),如果不知道索引就是O(n)

  • Set(index, e):O(1)

对于查找操作的时间复杂度:如果知道索引那么就是O(1),如果不知道索引就是O(n)

  • get(index):O(1)
  • contains(e):O(n)
  • find(e):O(n)

4.2 动态数组

对于动态数组的添加操作,只解释add(index, e),使用均摊时间复杂度来解释,假设数组的长度为10,那么使用addLast添加操作进行到第11次时会进行一次扩容,总共进行了21次操作。平均来看,每次addLast会进行2次(21除以10,约等于2)操作。

有了上面的结论,此时就可以总结:假设数组长度为n,那么进行到n+1次addFast会执行一次扩容,那么这过程的总操作数为2n+1(执行n次添加,加上1次扩容,扩容时执行n次复制),平均,每次addLast会进行2次操作

所以,可以得到addFast的均摊复杂度是O(1)。对于删除的操作也是这样来解释。

liuyubobo老师讲的:均摊时间复杂度,思想是对于一个耗时的操作,如果保证不会每次都触发,那么这个耗时的操作可以分摊到其他的操作中。


假设我们的缩容操作是到数组长度的1/2才缩容,目前数组长度为10,添加操作执行到11次时,此时长度会扩容2倍变成20,但此时再删除一个元素,又会缩容变成10,如果就在这两步间无限循环,扩容然后又缩容反复循环,那么就会出现复杂度震荡,也就是会导致添加和删除操作的时间复杂度为O(n)。

原因就是太急于缩容了,所以就出现了当元素个数为数组长度的1/4才缩容。

参考:

慕课网刘宇波老师

文章作者:flunggg

发布时间:2020年07月12日 - 23:07

原始链接:https://flunggg.cn/archives/5d6c5d62.html

许可协议: 转载请保留原文链接及作者。