不要小瞧数组！[数据结构与算法][Java]

  • 数据结构是所有计算机专业的同学必学的课程
  • 数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以高效的获取数据或者修改数据
  • 数据结构是所有计算机专业的同学必学的课程
  • 数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以高效的获取数据或者修改数据

我们需要根据应用的不同，灵活选择合适的数据结构

数据结构 + 算法 = 程序

面向面试

  1. 数组
  2. 栈
  3. 队列
  4. 链表
  5. 二分搜索树
  6. 堆

面向竞赛

  1. 线段树
  2. Trie
  3. 并查集

不要小瞧数组！

  • 数组的基础就是把数据码成一排进行存放
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
package cn.shuzu;
/**
 * 
 * @author HQF
 *
 */
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 == package cn.shuzu;
/**
 * 
 * @author HQF
 *
 */
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. 向数组中添加元素

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
package cn.shuzu;
/**
 * 
 * @author HQF
 *
 */
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;
	}
	
	//向所有元素后添加一个新元素
	public void addLast(int e) {
		add(size, 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("AddLast failed. Array is full."); 
		
		for (int i = size-1; i >= index; i --) 
			data[i+1] = data[i];
		
		data[index] = e;
		size++;
	}
	
	//向数组开头加添元素
	public void addFirst(int e) {
		add(package cn.shuzu;
/**
 * 
 * @author HQF
 *
 */
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;
	}
	
	//向所有元素后添加一个新元素
	public void addLast(int e) {
		add(size, 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("AddLast failed. Array is full."); 
		
		for (int i = size-1; i >= index; i --) 
			data[i+1] = data[i];
		
		data[index] = e;
		size++;
	}
	
	//向数组开头加添元素
	public void addFirst(int e) {
		add(0, e);
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package cn.shuzu;

public class Main {
    public static void main(String[] args) {

        Array arr = new Array(20);
        for (int i = 0; i < 10; i++) {
			arr.addLast(i);
		}
        System.out.println(arr);
        
        arr.add(1, 100);
        System.out.println(arr);

        arr.addFirst(-package cn.shuzu;

public class Main {
    public static void main(String[] args) {

        Array arr = new Array(20);
        for (int i = 0; i < 10; i++) {
			arr.addLast(i);
		}
        System.out.println(arr);
        
        arr.add(1, 100);
        System.out.println(arr);

        arr.addFirst(-1);
        System.out.println(arr);
    }
}

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

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
package cn.shuzu;

import java.awt.Container;

/**
 * 
 * @author HQF
 *
 */
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;
	}
	
	//向所有元素后添加一个新元素
	public void addLast(int e) {
		add(size, 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("AddLast failed. Array is full."); 
		
		for (int i = size-1; i >= index; i --) 
			data[i+1] = data[i];
		
		data[index] = e;
		size++;
	}
	
	//向数组开头加添元素
	public void addFirst(int e) {
		add(0, e);
	}
	
	//查找数组中是否有元素e
	public boolean container(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;
	}
	
	//删除元素
	public int remove(int index) {
		if (index < 0 || index >= size) 
			throw new IllegalArgumentException("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);
	}
	
	//查找数组中是否有指定元素，如果有则删除
	public void removeElement(int e)
	{
		int index = find(e);
		if (index != -1) {
			remove(index);
		}
	}
	
	//输出
	@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();
	}

	//获取index索引位置的元素
	int get(int index) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("Index is illegal.");
		}
		return data[index];
	}
	
	//对数组元素进行更新
	void set(int index,int e) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException(package cn.shuzu;

import java.awt.Container;

/**
 * 
 * @author HQF
 *
 */
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;
	}
	
	//向所有元素后添加一个新元素
	public void addLast(int e) {
		add(size, 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("AddLast failed. Array is full."); 
		
		for (int i = size-1; i >= index; i --) 
			data[i+1] = data[i];
		
		data[index] = e;
		size++;
	}
	
	//向数组开头加添元素
	public void addFirst(int e) {
		add(0, e);
	}
	
	//查找数组中是否有元素e
	public boolean container(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;
	}
	
	//删除元素
	public int remove(int index) {
		if (index < 0 || index >= size) 
			throw new IllegalArgumentException("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);
	}
	
	//查找数组中是否有指定元素，如果有则删除
	public void removeElement(int e)
	{
		int index = find(e);
		if (index != -1) {
			remove(index);
		}
	}
	
	//输出
	@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();
	}

	//获取index索引位置的元素
	int get(int index) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("Index is illegal.");
		}
		return data[index];
	}
	
	//对数组元素进行更新
	void set(int index,int e) {
		if (index < 0 || index >= size) {
			throw new IllegalArgumentException("Index is illegal.");
	}
		data[index] = e;
}
}

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
package cn.shuzu;

public class Main {
    public static void main(String[] args) {

        Array arr = new Array(20);
        for (int i = 0; i < 10; i++) {
			arr.addLast(i);
		}
        System.out.println(arr);
        
        arr.add(1, 100);
        System.out.println(arr);

        arr.addFirst(-1);
        System.out.println(arr);

        arr.remove(2);
        System.out.println(arr);

        arr.removeElement(package cn.shuzu;

public class Main {
    public static void main(String[] args) {

        Array arr = new Array(20);
        for (int i = 0; i < 10; i++) {
			arr.addLast(i);
		}
        System.out.println(arr);
        
        arr.add(1, 100);
        System.out.println(arr);

        arr.addFirst(-1);
        System.out.println(arr);

        arr.remove(2);
        System.out.println(arr);

        arr.removeElement(4);
        System.out.println(arr);
        
        arr.removeFirst();
        System.out.println(arr);
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
Array: size = 10,Capacity = 20
[0,1,2,3,4,5,6,7,8,9]
Array: size = 11,Capacity = 20
[0,100,1,2,3,4,5,6,7,8,9]
Array: size = 12,Capacity = 20
[-1,0,100,1,2,3,4,5,6,7,8,9]
Array: size = 11,Capacity = 20
[-1,0,1,2,3,4,5,6,7,8,9]
Array: size = 10,Capacity = 20
[-1,0,1,2,3,5,6,7,8,9]
Array: size = 9,Capacity = 20
[0,1,2,3,5,6,7,8,Array: size = 10,Capacity = 20
[0,1,2,3,4,5,6,7,8,9]
Array: size = 11,Capacity = 20
[0,100,1,2,3,4,5,6,7,8,9]
Array: size = 12,Capacity = 20
[-1,0,100,1,2,3,4,5,6,7,8,9]
Array: size = 11,Capacity = 20
[-1,0,1,2,3,4,5,6,7,8,9]
Array: size = 10,Capacity = 20
[-1,0,1,2,3,5,6,7,8,9]
Array: size = 9,Capacity = 20
[0,1,2,3,5,6,7,8,9]

使用泛型

  • 让我们的数据机构可以放置“任何”数据类型
  • 不可以是基本数据类型，只能是类对象。

(boolean, byte, char, short, int, long, float, double)

  • 每个基本数据类型都有相应的包装类

(Boolean, Byte, Char, Short, Int, Long, Float, Double)

动态数组

动态数组

在静态数组中如果数组满了就要进行动态扩容。

1
2
3
4
5
6
7
private void resize(int newCapacity) {
	E[] newData = (E[])new Object[newCapacity];
	for (int i = 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
public void add(int index,E e) {
 if (index<0 || index>size) 
		throw new IllegalArgumentException("AddLast failed. Array is full."); 
	
	if (size == data.length) 
		resize(2*data.length);	
		
	for (int i = size-1; i >= index; i --) 
		data[i+public void add(int index,E e) {
 if (index<0 || index>size) 
		throw new IllegalArgumentException("AddLast failed. Array is full."); 
	
	if (size == data.length) 
		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
//在移除数组元素的过程中，如果数组长度小于容量的一半就进行缩容
	public E remove(int index) {
		if (index < 0 || index >= size) 
			throw new IllegalArgumentException("Index is illegal.");
	E ret = data[index];
	for (int i = index+1; i < size; i++) {
		data[i-1] = data[i];
	}
	size--;
	data[size] = null;//loitering objects != memory leak
	
	if (size == data.length/2) {
		resize(data.length/2);
	}
	//在移除数组元素的过程中，如果数组长度小于容量的一半就进行缩容
	public E remove(int index) {
		if (index < 0 || index >= size) 
			throw new IllegalArgumentException("Index is illegal.");
	E ret = data[index];
	for (int i = index+1; i < size; i++) {
		data[i-1] = data[i];
	}
	size--;
	data[size] = null;//loitering objects != memory leak
	
	if (size == data.length/2) {
		resize(data.length/2);
	}
	return ret;
	}

简单的时间复杂度分析

  • O（1），O（n），O（lgn），O（logn），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 += num;
		
	public static int sum(int[] nums){
	int sum = 0;
	for(int num:nums)
		sum += num;
		
	return sum;
}
  • 时间复杂度O（n），n是nums中的元素个数，算法和n呈线性关系

为什么要用大O，叫做O（n）？

忽略常数。实际时间T = c1*n + c2

1
2
3
T = 2*n	+ 2 		  O(n)
T = 2000*n + 10000	  O(n)
T = 1*n*n + 0		 O(n^T = 2*n	+ 2 		  O(n)
T = 2000*n + 10000	  O(n)
T = 1*n*n + 0		 O(n^2)

针对数组进行复杂度分析

addLast(e) O(1)

addFirst(e) O(n)

add(index,e) O(n/2) = O(n)

严格计算需要一些概率论知识。