数组

数据结构

数组

数组基础

把数据码成一排进行存放

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Main {
    public static void main(String[] args) {
        int[] arr =new int[10];
        for (int i=0;i<arr.length;i++){
            arr[i]=i;
        }
        System.out.println("---");
        int[] scores =new int[]{1,2,3};
        for (int i=0;i<scores.length;i++){
            System.out.println(scores[i]);
        }
        System.out.println("---");
        for (int score:scores){
            System.out.println(score);
        }
        System.out.println("---");
        scores[0]=96;
        for (int i=0;i<scores.length;i++){
            System.out.println(scores[i]);
        }
    }
}

输出结果

1
2
3
4
5
6
7
8
9
10
11
12
---
1
2
3
---
1
2
3
---
96
2
3

数组的最大优点：快速查询，例如scores[2]

数组最好应用于“索引有语意”的情况，但并非所有语意的索引都适用于数组

自定义数组

设计数组的类叫做class Array，里面封装一个data数组，包含增删改查，数组的容量为capacity，实际容量为size，初始时size为0

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
30
public class Array {
    private int[] data;
    private int size;

    //构造函数，传入数组的容量capacity构造Array
    public Array(int capacity){
        data=new int[capacity];
        size=0;
    }

    //无参数的构造函数，默认数组的容量capacity=10
    public Array(){
        this(10);
    }

    //获取数组中的元素个数
    public int getSize(){
        return size;
    }

    //获取数组的容量
    public int getCapacity(){
        return data.length;
    }

    //返回数组是否为空
    public boolean isEmpty(){
        return size==0;
    }
}

向数组中添加元素

向数组末尾添加元素

1
2
3
4
5
6
7
public void addLast(int 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
//在index个位置插入一个新元素e
public void add(int index,int e){
    if (size==data.length) {
    	throw new IllegalArgumentException("AddLast failed.Array is full.");
    }

    if (index<0||index>size) {
   		throw new IllegalArgumentException("Add failed.Require index >= 0 and index <= size.");
    }

    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
//向所有元素后添加一个新元素
public void addLast(int e){
    /*if (size==data.length) {
            throw  new IllegalArgumentException("AddLast failed.Array is full.");
        }
        data[size]=e;
        size++;*/
    add(size,e);
}

向所有元素前添加元素可写为

1
2
3
4
//向所有元素前添加元素
public void addFirst(int e){
    add(0,e);
}

在数组中查询元素和修改元素

查询元素

1
2
3
4
5
6
7
//获取index索引位置的元素
public int 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
//修改index索引位置的元素e
public void set(int index,int e){
    if (index<0||index>=size) {
        throw new IllegalArgumentException("Get failed.Index is illegal");
    }
    data[index]=e;
}

toString方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
@Override
public String toString(){
    StringBuffer res = new StringBuffer();
    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();
}

在数组中的包含，搜索和删除元素

数组中的包含

查询数组中是否有元素e

1
2
3
4
5
6
7
8
9
//查询数组中是否有元素e
public boolean contains(int e
    for (int i=0;i<size;i++){
    	if (data[i]==e){
    	return true;
    	}
    }
    return false;
}

查找数组中元素e所在的索引，如果不存在元素e，则返回-1

1
2
3
4
5
6
7
8
9
//查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(int e){
    for (int i=0;i<size;i++){
    	if (data[i]==e){
    	return i;
    	}
    }
    return -1;
}

从数组中删除元素

数组在开辟空间的时候所有的位置都有一个默认值0，对用户是不可见的，用户根本不需要管初始值是多少，只需要关注用户添加了什么元素

image-20200213103428450image-20200213103532503image-20200213103428450image-20200213103532503

image-20200213103619290image-20200213103705762image-20200213103619290image-20200213103705762

image-20200213103735675 image-20200213103809004 
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
//从数组中删除index位置的元素，返回删除的元素
public int remove(int index){
    if (index<0||index>size) {
        throw new IllegalArgumentException("Remove failed.Index is illegal");
    }

    int ret=data[index];
    for(int i=index+1;i<size;i++){
        data[i-1]=data[i];
    }
    size--;
    return ret;
}

//从数组中删除第一个元素，返回删除的元素
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);
    }
}

使用泛型

让我们的数据结构可以放置“任何”数据类型，不可以是基本数据类型，只能是类对象，每个基本数据类型都有对应的包装类

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
/**
 * E表示的是数据类型，Array的数据类型是E，具体是什么，可以在使用的时候声明
 */
public class Array<E> {
    private E[] data;
    private int size;

    //构造函数，传入数组的容量capacity构造Array
    public Array(int capacity){
        data=(E[])new Object[capacity];
        size=0;
    }

    //无参数的构造函数，默认数组的容量capacity=10
    public Array(){
        this(10);
    }

    //获取数组中的元素个数
    public int getSize(){
        return size;
    }

    //获取数组的容量
    public int getCapacity(){
        return data.length;
    }

    //返回数组是否为空
    public boolean isEmpty(){
        return size==0;
    }

    //向所有元素后添加一个新元素
    public void addLast(E e){
        /*if (size==data.length) {
            throw  new IllegalArgumentException("AddLast failed.Array is full.");
        }
        data[size]=e;
        size++;*/
        add(size,e);
    }

    //向所有元素前添加元素
    public void addFirst(E e){
        add(0,e);
    }

    //在index个位置插入一个新元素e
    public void add(int index,E e){
        if (size==data.length) {
            throw new IllegalArgumentException("AddLast failed.Array is full.");
        }

        if (index<0||index>size) {
            throw new IllegalArgumentException("Add failed.Require index >= 0 and index <= size.");
        }

        for (int i=size-1;i>=index;i--){
            data[i+1]=data[i];
        }
        data[index]=e;
        size++;
    }


    @Override
    public String toString(){
        StringBuffer res = new StringBuffer();
        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();
    }

    //获取index索引位置的元素
    public E get(int index){
        if (index<0||index>=size) {
            throw new IllegalArgumentException("Get failed.Index is illegal");
        }
        return data[index];
    }

    //修改index索引位置的元素e
    public void set(int index,E e){
        if (index<0||index>=size) {
            throw new IllegalArgumentException("Get failed.Index is illegal");
        }
        data[index]=e;
    }

    //查询数组中是否有元素e
    public boolean contains(E e){
        for (int i=0;i<size;i++){
            if (data[i].equals(e)){
                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;
    }

    //从数组中删除index位置的元素，返回删除的元素
    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]=null;
        return ret;
    }

    //从数组中删除第一个元素，返回删除的元素
    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);
        }
    }
}

测试类

1
2
3
4
5
6
7
8
9
public class Main {
    public static void main(String[] args) {
        Array<Integer> arr1 = new Array();
        for (int i=0;i<10;i++){
            arr1.addLast(i);
        }
        System.out.println(arr1);
    }
}

动态数组

image-20200213115009335

扩容数组

1

image-20200213115157108

2

image-20200213130016890

3

image-20200213130121568

4

image-20200213130210841 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//在index个位置插入一个新元素e
public void add(int index,E e){
    if (size==data.length) {
        resize(2*data.length);
    }

    if (index<0||index>size) {
        throw new IllegalArgumentException("Add failed.Require index >= 0 and index <= size.");
    }

    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
private void resize(int newCapacity) {
    E[] newData = (E[]) new Object[newCapacity];
    for(int i=0;i<size;i++){
        newData[i]=data[i];
    }
    //将newData的引用交给data
    data=newData;
}

数组缩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//从数组中删除index位置的元素，返回删除的元素
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]=null;
    if (size==data.length/2) {
        resize(data.length/2);
    }
    return ret;
}

简单的时间复杂度分析

O(1)、O(n)、O(lgn)、O(nlogn)、O(n^2)

简单的来说，大O描述的是算法的运行时间和输入数据之间的关系

1
2
3
4
5
6
7
public static int sum(int[] nums){
    int sum=0;
    for (int num:nums){
        sum+=sum;
    }
    return sum;
}

上面的程序的时间复杂度为O(n)，n是nums中的元素个数，算法和n呈线性关系

为什么要用大O，为什么叫做O(n)？

因为实际上忽略了常数，实际时间为T=c1*n+c2

例如：

时间复杂度
T=2*n+2 O(n)
T=2000*n+10000 O(n)
T=1*n*n+0 O(n^2)
T=2*n*n+300n+10 O(n^2)

渐进时间复杂度，描述n趋近于无穷的情况

分析动态数组的时间复杂度

添加操作 O(n)
addLast(e) O(1)
addFirst(e) O(n)
add(index,e) O(n/2)=O(n)
resize() O(n)
image-20200213172256720

删除操作 O(n)

image-20200213172411312

修改操作 O(1)

image-20200213172511572

查询操作

image-20200213172607609

总结

resize的复杂度分析

假设当前capacity=8，并且每一次添加操作都使用addLast，即

image-20200213180721764

9次addLast操作，触发resize，总共进行17（8+9）次基本操作，平均每次addLast操作，进行2次基本操作

假设capacity=n，n+1次addLast，触发resize，总共进行2n+1次基本操作，平均每次addLast操作，进行2次基本操作，这样均摊计算，时间复杂度是O(1)的

这个例子里这样均摊计算，比计算最坏情况有意义

均摊复杂度 amortized time complexity

addLast的均摊复杂度是O(1)

同理，removeLast操作，均摊复杂度也是O(1)

复杂度震荡

当我们同时看addLast和removeLast操作，就会发生复杂度震荡

出现问题的原因是因为removeLast时resize过于着急（Eager）

解决方案，使用懒加载方案（Lazy），当size==capacity/4时，才将capacity减半

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//从数组中删除index位置的元素，返回删除的元素
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]=null;
    if (size==data.length/4&&data.length/2!=0) {
        resize(data.length/2);
    }
    return ret;
}

注

得到第一个和最后一个元素

1
2
3
4
5
6
7
8
9
public E getLast(){
    return get(size-1);
    //不这样写的原因是若size=0，则不合法，使用get方法能利用get方法中的条件判断
    //return data[size-1];
}

public E getFirst(){
    return get(0);
}

本文标题:数组

文章作者:爱吃鱼的呆先生

发布时间:2020-03-15, 09:50:22

最后更新:2020-02-21, 11:14:00

原始链接:http://yoursite.com/2020/03/15/数据结构/1数组/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 数组
    1. 1.1. 数组基础
    2. 1.2. 自定义数组
    3. 1.3. 向数组中添加元素
      1. 1.3.1. 向数组末尾添加元素
      2. 1.3.2. 向指定位置添加元素
    4. 1.4. 在数组中查询元素和修改元素
    5. 1.5. toString方法
    6. 1.6. 在数组中的包含，搜索和删除元素
      1. 1.6.1. 数组中的包含
        1. 1.6.1.1. 查询数组中是否有元素e
        2. 1.6.1.2. 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
      2. 1.6.2. 从数组中删除元素
      3. 1.6.3. 使用泛型
      4. 1.6.4. 动态数组
      5. 1.6.5. 简单的时间复杂度分析
        1. 1.6.5.1. 分析动态数组的时间复杂度
      6. 1.6.6. resize的复杂度分析
      7. 1.6.7. 复杂度震荡
      8. 1.6.8. 注
|